Cho ~Q~ truy vấn, mỗi truy vấn gồm một số nguyên dương ~N~.

Với mỗi truy vấn, bạn cần đếm số lượng các bộ số (~A~, ~B~, ~C~) (~1 \le A < B < C \le N~) sao cho ~A \times B~, ~B \times C~, ~C \times A~ đều là các số chính phương.

Nhắc lại, một số ~x~ là số chính phương khi và chỉ khi tồn tại một số nguyên ~y~ sao cho ~y^2 = x~.

INPUT

Dòng đầu tiên chứa số nguyên dương ~Q~ (~1 \le Q \le 5 \times 10^6~) là số lượng truy vấn.

~Q~ dòng tiếp theo, mỗi dòng bao gồm một số nguyên dương ~N~ (~1 \le N \le 10^7~) mô tả một truy vấn.

Dữ liệu đảm bảo kết quả của mỗi truy vấn không vượt quá ~2^{60} - 1~.

OUTPUT

Để giảm kích thước đầu ra, hãy in ra tổng XOR mọi kết quả qua từng truy vấn.

Phép ~XOR~ trong các ngôn ngữ có thể thực hiện như sau:

• C++: ^.
• Python: ^.
• Pascal: XOR.
• Java: ^.

SAMPLE INPUT

2
20
30

SAMPLE OUTPUT

9

Với test đầu tiên, có ~5~ bộ thỏa mãn là ~(1,4,9)~, ~(1,4,16)~, ~(1,9,16)~, ~(2,8,18)~, ~(4,9,16)~.

Tương tự như vậy, với test thứ hai có ~12~ bộ thỏa mãn.

Vì vậy, ta in ra ~5~ ~XOR~ ~12~ ~=~ ~9~.

SUBTASKS