Cho N. Tìm số i (1 <= i <= N) có số lượng ước số lớn nhất. Nếu có nhiều số i có cùng số lượng ước lớn nhất, hãy in ra số i nhỏ nhất. Gợi ý: Nếu n = p1^a1 x p2^a2, thì d(n) = (a1+1) x (a2+1).

Input:

Một dòng duy nhất chứa số nguyên N (1 <= N <= 100000).

Output:

In ra số i có nhiều ước nhất.

Test Case 1:

Input:

10

Output:

6

(Giải thích: 6, 8, 10 đều có 4 ước. Chọn 6 vì nhỏ nhất)

Một cặp SNT sinh đôi là một cặp số nguyên tố (p, p+2). Cho một số nguyên N. Hãy đếm số lượng cặp SNT sinh đôi (p, p+2) sao cho p+2 <= N.

Input:

Một dòng duy nhất chứa số nguyên N (5 <= N <= 1000000).

Output:

In ra số lượng cặp SNT sinh đôi thỏa mãn.

Test Case 1:

Input:

15

Output:

3

(Giải thích: Các cặp là (3, 5), (5, 7), (11, 13))

Một số được gọi là "Square-Free" nếu nó không chia hết cho bất kỳ số chính phương nào lớn hơn 1. Cho Q truy vấn, hãy kiểm tra xem n có phải là Square-Free hay không.

Dữ liệu vào: Dòng đầu chứa Q. Q dòng sau chứa n.

Dữ liệu ra: In ra "YES" nếu n là Square-Free, ngược lại in "NO".

Ràng buộc: 1 <= Q <= 100000 1 <= n <= 1000000

Ví dụ 1:

Input:

3 
10 12 1

Output:

YES 
NO 
YES

Ví dụ 2:

Input:

2 18 7

Output:

NO 
YES

Cho Q truy vấn n. Tính tổng các số nguyên dương k <= n sao cho GCD(k, n) = 1.

Dữ liệu vào: Dòng đầu chứa Q. Q dòng sau chứa n.

Dữ liệu ra: Q dòng kết quả.

Ràng buộc: 1 <= Q <= 100000 1 <= n <= 1000000

Ví dụ 1:

Input:

2 5 10

Output:

10 20

Ví dụ 2:

Input:

1 4

Output:

4

Cho dãy n số.

Với mỗi phần tử ai, in ra số lần nó đã xuất hiện trước đó trong dãy.

Input:

n

a1 a2 ... an

Output:

In n số cách nhau bởi dấu cách — số lần xuất hiện trước đó của từng ai.

Constraints:

1 ≤ n ≤ 10^5

1 ≤ ai ≤ 10^9

Sample:

Input:

5
2 1 2 2 1

Output:

0 0 1 2 1