Cho số nguyên dương ~n~. Tìm ước số lẻ lớn nhất của ~n~ nhỏ hơn ~n~.

Input

• Dòng đầu ghi số nguyên dương ~T~ là số bộ test;
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n~.

Giới hạn:

• ~1 ≤ T ≤ 10^5, 2 ≤ n ≤ 10^6~.

Output

• Với mỗi số nguyên dương ~n~, ghi ra trên một dòng ước số lẻ lớn nhất của ~n~ nhỏ hơn ~n~.

Sample

Input #1

3
3
8
15

Output #1

1
1
5

Problem source: Chuyên Sơn La Online Judge

Tính tổng các chữ số của số nguyên dương trong hệ thập phân.

Input

• Dòng đầu ghi số nguyên dương ~T~ là số bộ test;
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n~ ghi ở hệ thập phân.

Giới hạn:

• ~1≤T≤10^5,1≤n≤10^{18}~

Output

• Với mỗi bộ test, ghi ra trên một dòng một số là tổng các chữ số của số ~n~ tương ứng.

Sample

Input #1

2
13
256

Output #1

4
13

Problem source: Chuyên Sơn La Online Judge

Cho một dãy gồm ~n~ số nguyên, hãy đếm số cặp bằng nhau trong dãy

Input

• Dòng đầu tiên chứa duy nhất một số nguyên dương ~n~ (số phần tử trong dãy).
• Dòng thứ hai chứa n số nguyên là các phần tử ~a_1,a_2,…,a_n~

Giới hạn:

• ~1≤n≤10^5,0≤a_i≤5.10^4~

Output

• In ra trên một dòng số nguyên không âm là số cặp bằng nhau liên tiếp trong dãy.

Sample

Input #1

4
3 1 2 3

Output #1

1

Input #2

5
4 1 1 2 2

Output #2

2

Input #3

6
5 3 1 2 1 1

Output #3

3

Problem source: Chuyên Sơn La Online Judge

Cho số nguyên dương ~n~. Hãy phân tích ~n~ ra thừa số nguyên tố. Tức là tìm các số nguyên tố ~p_1, p_2, …, p_k~ đôi một phân biệt và các số nguyên dương ~α_1, α_2, …, α_k~ sao cho:$$n = {p_1}^{{\alpha _1}} \times {p_2}^{{\alpha _2}} \times ... \times {p_k}^{{\alpha _k}}$$

Input

• Gồm một dòng duy nhất chứa số nguyên dương ~n~.

Giới hạn:

• ~1 ≤ n ≤ 10^{12}~.

Output

• Dòng đầu ghi số nguyên dương ~k~
• ~k~ dòng sau, dòng thứ ~i~ ghi hai số ~p_i~ và ~α_i~ cách nhau một dấu cách, các số ~p_i~ được sắp xếp tăng dần.

Sample

Input #1

10

Output #1

2
2 1
5 1

Input #2

12

Output #2

2
2 2
3 1

Hint

• ~10 = 2^1 × 5^1~
• ~12 = 2^2 × 3^1~

Problem source: Chuyên Sơn La Online Judge