Cho ~N~ số nguyên dương ~a_1,a_2,…,a_N~. Với mỗi giá trị ~a_i, ∀i=1..N~, hãy cho biết ~a_i~ có bao nhiêu ước số?

Input

• Dòng đầu chứa một số nguyên dương ~N~;
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1,a_2,…,a_N~.

Giới hạn:

• ~60\%~ số điểm ứng với các test có ~N≤1000,1≤a_i≤10^3, ∀i=1..N~;
• ~40\%~ số điểm ứng với các test có ~N≤1000,1≤a_i≤10^8, ∀i=1..N~.

Output

• Ghi trên ~N~ dòng, dòng thứ ~i~ ghi số ước số của ~a_i~.

Sample

Input #1

6
2 3 5 7 4 8

Output #1

2
2
2
2
3
4

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