Bài tập

Cho dãy gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\). Ở mỗi bước, bạn chọn hai phần tử bất kỳ của dãy, rồi lấy phần tử có giá trị lớn hơn trừ đi giá trị của phần tử nhỏ hơn (giá trị của phần tử nhỏ hơn giữ nguyên). Nếu hai phần tử bằng nhau thì thao tác không thay đổi gì.

Bạn được thực hiện số bước tùy ý (kể cả không bước nào), và các phần tử luôn phải là số nguyên dương. Hãy tìm tổng nhỏ nhất có thể của các phần tử trong dãy.

Input

• Dòng đầu chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, \dots, a_n\).

Output

• In ra tổng nhỏ nhất của dãy sau khi thực hiện các thao tác.

Constraints

• \(1 \le n \le 10^5\)
• \(1 \le a_i \le 10^9\)

Sample Input

4
9 15 6 21

Sample Output

12

Explanation

Ước chung lớn nhất của dãy là \(3\); có thể đưa mọi phần tử về \(3\), tổng là \(4 \times 3 = 12\).

Tổng các chữ số của một số nguyên không âm \(n\) là tổng của tất cả các chữ số trong biểu diễn thập phân của \(n\). Ví dụ tổng các chữ số của \(405\) là \(4+0+5=9\).

Cho dãy \(n\) số nguyên không âm \(A_1, A_2, \ldots, A_n\). Với mỗi phần tử, hãy in ra chính số đó kèm theo tổng các chữ số của nó.

Gợi ý: viết hàm \(SumDigit(n)\) trả về tổng các chữ số của \(n\).

Input

• Dòng đầu chứa số nguyên \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(A_1, A_2, \ldots, A_n\).

Output

• In ra \(n\) dòng; dòng thứ \(i\) gồm số \(A_i\) và tổng các chữ số của nó, cách nhau một dấu cách.

Constraints

• \(1 \le n \le 10^5\)
• \(0 \le A_i \le 10^{18}\)

Sample Input 1

4
405 7 99999 0

Sample Output 1

405 9
7 7
99999 45
0 0

Cho dãy \(n\) số nguyên không âm \(a_1, a_2, \dots, a_n\) và một số nguyên \(m \ge 2\). Hãy cho biết có thể chọn ra một số phần tử của dãy (ít nhất một phần tử, không nhất thiết liên tiếp) sao cho tổng các phần tử được chọn chia hết cho \(m\) hay không.

Input

• Dòng đầu chứa hai số nguyên \(n\) và \(m\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\).

Output

In ra YES nếu tồn tại cách chọn thoả mãn, ngược lại in NO.

Constraints

• \(1 \le n \le 10^6\)
• \(2 \le m \le 10^3\)
• \(0 \le a_i \le 10^9\)

Sample Input 1

4 7
3 5 6 1

Sample Output 1

YES

Sample Input 2

2 10
3 4

Sample Output 2

NO

Sample Input 3

3 8
5 5 5

Sample Output 3

NO

Explanation

Ở ví dụ 1 chọn \(6\) và \(1\) có tổng \(7\). Ở ví dụ 2 các tổng có thể là \(3, 4, 7\), không có tổng nào chia hết cho \(10\). Ở ví dụ 3 các tổng có thể là \(5, 10, 15\), không chia hết cho \(8\).

Với mỗi số nguyên dương \(n\) cho trước, hãy cộng tất cả các ước dương của \(n\) (kể cả \(1\) và chính \(n\)) và cho biết tổng đó.

Input

• Dòng đầu tiên chứa số nguyên \(T\) là số lượng câu hỏi.
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(n\).

Output

Với mỗi câu hỏi, in ra trên một dòng tổng các ước dương của \(n\).

Constraints

• \(1 \le T \le 200\)
• \(1 \le n \le 10^{12}\)

Sample Input

3
12
17
100

Sample Output

28
18
217

Explanation

Các ước của \(12\) là \(1, 2, 3, 4, 6, 12\) có tổng \(28\). Số \(17\) là số nguyên tố nên có tổng \(1 + 17 = 18\).