Các sinh vật phải vượt qua một bài vô cùng hóc búa từ Ngọc Hoàng, bài toán được phát biểu như sau:

Cho một dãy số ~n~ số nguyên dương ~a_1, a_2,\ldots, a_n~. Với mỗi số nguyên dương ~a_i~, thí sinh cần đếm xem có bao nhiêu nghiệm nguyên của phương trình ~x + y + gcd(x, y) = a_i~.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \leq n \leq 2 \cdot 10^5~).

Dòng tiếp theo chứa ~n~ số nguyên dương ~a_i~ (~1 \leq a_i \leq 4 \cdot 10^6~).

Output

Một dòng duy nhất chứa ~n~ số nguyên dương là đáp án của bạn.

Scoring

Sample Input 1

3
6 10 13

Sample Output 1

5 8 4

Sample Input 2

6
327 869 541 985 214 736

Sample Output 2

199 388 144 406 192 974

Sample Input 3

4
3278695 419852 1473646 1537928

Sample Output 3

1595840 579790 1107994 2819626

Notes

Trong ví dụ thứ nhất:

• Với ~n = 6~ ta có ~\textbf{5}~ cặp số: $$(1, 4), (2, 2), (2, 3), (3, 2), (4, 1).$$

• Với ~n = 10~ ta có ~\textbf{8}~ cặp số: $$(1, 8), (2, 6), (2, 7), (4, 5), (5, 4), (6, 2), (7, 2), (8, 1).$$

• Với ~n = 13~ ta có ~\textbf{4}~ cặp số: $$(1, 11), (5, 7), (7, 5), (11, 1).$$