Cho \(n\) số nguyên. Với mỗi số, hãy đếm số ước nguyên dương của nó.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 10^5\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(x\) (\(1 \le x \le 10^6\)).

Dữ liệu ra

• Gồm \(n\) dòng, dòng thứ \(i\) là số ước nguyên dương của số thứ \(i\) trong dãy.

Ví dụ

Input:

3
16
17
18

Output:

5
2
6

Giải thích:

• Số \(16\) có các ước: \(1, 2, 4, 8, 16\) → \(5\) ước.
• Số \(17\) là số nguyên tố, có các ước: \(1, 17\) → \(2\) ước.
• Số \(18\) có các ước: \(1, 2, 3, 6, 9, 18\) → \(6\) ước.

Ràng buộc

• \(1 \le n \le 10^5\)
• \(1 \le x \le 10^6\)

Subtask

• Subtask 1 (35.29% điểm): \(n \le 1000\), \(x \le 10000\).
• Subtask 2 (64.71% điểm): Không có ràng buộc gì thêm.