Cho ~n~ và dãy số nguyên ~a1, a2, ..., an~. Với mỗi ~i (1..n)~ hãy cho biết số lượng ước số và tổng các ước số của ~ai~.

Input

• Dòng ~1~: số nguyên dương ~n (n \le 10^6)~;
• Dòng ~2~: Ghi ~n~ số nguyên dương ~a1, a2, ..., an (ai \le 10^5)~. (các số ghi trên một dòng cách nhau một dấu cách)

Output: Ghi trên ~n~ dòng

• Dòng ~i~ gồm ~2~ số nguyên là số lượng ước số và tổng ước số của ~ai~ tương ứng. (các số ghi trên một dòng cách nhau một dấu cách)

Sample input

6
1 2 3 4 5 6

Sample output

1 1
2 3
2 4
3 7
2 6
4 12

Subtask

• ~50\%~ số test có ~n \le 10^2~

• ~50\%~ số test còn lại không có điều kiện gì thêm