Trong chương trình trải nghiệm "Thái Nguyên - Thủ đô gió ngàn - Vẻ đẹp tiềm ẩn", trường THCS Hoa Sen tổ chức cho học sinh đi trải nghiệm tại các khu di tích lịch sử, du lịch sinh thái trong tỉnh Thái Nguyên.

Tại không gian văn hóa chè Tân Cương, mỗi bạn học sinh khi vào cổng tham quan sẽ được phát một tấm vé có in một số nguyên dương. Để tăng thêm tính hấp dẫn, Ban tổ chức thông báo: "Những học sinh sở hữu tấm vé có "Mã số đặc biệt" sẽ nhận được một phần quà từ Ban tố chức"

Một mã số được coi là "Mã số đặc biệt" nếu tổng các chữ số của nó chia hết cho số lượng chữ số của chính nó. Ví dụ: mã số 132 là "Mã số đặc biệt" vì: tổng các chữ số của 132 là 1 + 3 + 2 = 6, số lượng các chữ số là 3 (6 chia hết cho 3); mã số 251 không phải là "Mã số đặc biệt" vì: tổng các chữ số của 251 là 2 + 5 + 1 = 8, số lượng các chữ số là 3 (8 không chia hết cho 3).

Yêu cầu: Hãy viết chương trình đếm xem có bao nhiêu bạn học sinh may mắn trúng thưởng và nhận được phần quà từ Ban tổ chức.

Dữ liệu: Đọc từ thiết bị chuẩn (bàn phím) một số nguyên dương n (1 ≤ n ≤ 10^6).

Kết quả: Ghi ra thiết bị chuẩn (màn hình) số nguyên dương duy nhất là số lượng số đặc biệt không vượt quá n.

Ví dụ:

Input:

15

Output:

12

Giải thích: Từ 1 đến 15 có 12 số: 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, thỏa mãn yêu cầu.

Các số 10, 12, 14 không thỏa mãn vì cà hai số có số lượng chữ số là 2, tổng các chữ số: 1 + 0 = 1, 1 + 2 = 3, 1 + 4 = 5 đều không chia hết cho 2.

Ràng buộc:

• Có 30% số điểm thỏa mãn 1 ≤ n < 10;

• Có 70% số điểm thỏa mãn 10 ≤ n ≤ 10^6

Vẫn trong chương trình trải nghiệm của trường THCS Hoa Sen, tại khu du lịch Hồ Núi Cốc, Ban tổ chức thiết kế trò chơi "Vượt chướng ngại vật" gồm nhiều chặng được đặt tại các khu vui chơi. Những bạn học sinh vượt qua tất cả các chướng ngại vật sẽ nhận được phân quà từ Ban tồ chức. Tại mỗi chặng, chướng ngại vật là một xâu kí tự S chứa các kí tự tiếng Anh in thường (không chứa kí tự trắng), chỉ những bạn học sinh trả lời đúng câu hỏi: "Có thế tạo được xâu cân bằng bằng cách xóa tối đa một kí tự trong xâu S hay không?" mới được di chuyển tới chặng tiếp theo.

Một xâu được gọi là "Xâu cân bằng" nếu số lần xuất hiện của tất cả các chữ cái trong xâu đều bằng nhau. Ví dụ: Xâu "aabb" là xâu cân bằng vì cả kí tự "a" và "b" đều xuất hiện 02 lần. Xâu "aaabb" không phải là xâu cân bằng vì kí tự "a" xuất hiện 03 lần còn kí tư "b" xuất hiện 02 lần.

Yêu cầu: Cho q xâu kí tự S có độ dài không quá 10^5. Hãy đưa ra câu trả lời cho câu hỏi: "Có thể tạo được một xâu cân bằng bằng cách xóa tối đa một kí tự trong xâu đã cho hay không?

Dữ liệu: Đọc từ thiết bị chuẩn (bàn phím):

• Dòng đầu tiên chứa số lượng truy vấn 1 ≤ q < 10^2.

• q dòng tiếp theo, mỗi dòng chứa một xâu kí tự S.

Kết quả: Ghi ra thiết bị chuẩn (màn hình) q dòng, mỗi dòng ghi "YES" nếu có thể xóa tối đa một kí tự trong xâu S để S trở thành xâu cân bằng, ngược lại ghi "NO".

Input:

5
a
aabaa
abc
baaccc
aacbccb

Output:

YES
YES
YES
NO
YES

Ràng buộc:

• Có 40% số điểm thoa mãn q = 1, độ dài xâu S nhỏ hơn 10^4;

• Có 60% số điểm còn lại thỏa mãn 1 < q ≤ 10^2 và độ dài xâu S nhỏ hơn 10^5.

Địa điểm tiếp theo trong chương trình trải nghiệm của trường THCS Hoa Sen là Di tích ATK (xã Phú Đình), Ban tổ chức đã chuẩn bị một thử thách như sau: Tại gian hàng trưng bày đồ lưu niệm có n món đồ có giá trị lần lượt từ 1 đến n được trưng bày theo thứ tự từ trái sang phải và nhiều phần quà ý nghĩa có giá trị K (2 ≤ K ≤ 10^5). Thử thách Ban tổ chức đưa ra như sau: Xác định số lượng các cặp (i; j) sao cho tổng các món đồ lưu niệm liên tiếp có giá trị từ i đến j (1 ≤ i ≤ j ≤ n) chia hết cho K.

Mỗi bạn học sinh hoàn thành thử thách sẽ nhận được một phần quà có giá trị K.

Yêu cầu: Hãy viết chương trình giúp các bạn học sinh vượt qua thử thách của Ban tổ chức.

Dữ liệu: Đọc từ thiết bị chuẩn (bàn phím) hai số nguyên dương n và K cách nhau một kí tự trắng, (1≤ n ≤ 10^9,1 ≤ K ≤ 10^5).

Kết quả: Ghi ra thiết bị chuẩn (màn hình) số nguyên duy nhất là số lượng cặp (i; j) thỏa mãn yêu cầu.

Ví dụ:

Input:

5 4

Output:

2

Giải thích:

n = 5, k = 4, có 2 cặp số (i;j) là (4;4) và (3;5) có tổng chia hết cho k.

Với (i;j) = (4;4), tính tổng các số trong đoạn [4,4] được kết quả là 4 (chia hết cho k = 4).

Với (i;j) = (3;5), tính tổng các số trong đoạn [3, 5], ta có: 3 + 4 + 5 = 12 (chia hết cho k = 4)

Ràng buộc:

• Có 40% số điểm thoa mãn 1 ≤ n ≤ 10^3;

• Có 30% số điểm thỏả mãn 10^3 ≤ n ≤ 10^5;

• Có 30% số điểm thỏa mãn 10^5 ≤ n ≤ 10^9