Một số nguyên dương N (không phải số nguyên tố) được gọi là số Smith nếu tổng các chữ số của N bằng tổng các chữ số của các thừa số nguyên tố của N (tính cả bội số). Kiểm tra N có phải số Smith không.

Dữ liệu vào:

Dòng 1: Q (1 <= Q <= 10^5).

Q dòng tiếp theo: N (4 <= N <= 10^7).

Dữ liệu ra:

In 1 nếu là số Smith, ngược lại in 0.

Ví dụ:

Input:

1 
4937775

Output:

1

Giải thích: 4937775 = 3 * 5 * 5 * 65837. Tổng chữ số: 4+9+3+7+7+7+5 = 42. Tổng chữ số các thừa số: 3 + 5 + 5 + (6+5+8+3+7) = 42.

Cho mảng A có N phần tử. Tìm một đoạn con liên tiếp có độ dài ít nhất là K sao cho giá trị trung bình các phần tử trong đoạn con là lớn nhất. (Gợi ý: Chặt nhị phân trên giá trị trung bình, chuyển bài toán thành kiểm tra tổng (A[i] - X) >= 0).

Dữ liệu vào:

Dòng 1: Hai số nguyên N và K (1 <= K <= N <= 10^5).

Dòng 2: N số nguyên A[i] (|A[i]| <= 10000).

Dữ liệu ra:

Giá trị trung bình lớn nhất (in 3 chữ số thập phân).

Ví dụ:

Input:

4 2 
10 20 30 40

Output:

35.000

Cho mảng A gồm N phần tử và số K. Với mỗi phần tử Ai, hãy tính GCD(Ai, K). Sau đó in ra tổng của các kết quả này.

Dữ liệu vào:

Dòng 1: N, K (1 <= N <= 10^5, 1 <= K <= 10^6).

Dòng 2: Mảng A (1 <= Ai <= 10^6).

Dữ liệu ra:

Tổng các GCD.

Ví dụ:

Input:

3 6 
2 3 4

Output: 7

Giải thích: gcd(2,6)=2, gcd(3,6)=3, gcd(4,6)=2. Tổng = 7.

Nhập vào 1 số nguyên dương N, in ra tổng các chữ số của nó.

Input: Nhập vào số nguyên dương N (1 ≤ N ≤ 10^100000).

Output: In ra tổng các chữ số của N.

Ví dụ:

Input:

2451992

Output:

32

Cho hai chuỗi word1 và word2. Tìm số thao tác tối thiểu để chuyển đổi word1 thành word2. Bạn được phép thực hiện ba thao tác sau trên một từ:

• Insert a character

• Delete a character

• Replace a character

Input:

• Bao gồm hai dòng: dòng 1 chứa word1, dòng 2 chứa word2

• 0 <= word1.length, word2.length <= 500

Output:

Gồm 1 dòng chứa 1 số nguyên là số thao tác tối thiểu để chuyển đổi word1 thành word2.

Ví dụ :

Input:

horse
ros

Output:

3

Giải thích: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e')