Trong khi Loli và Minh đi trên đường cao tốc, để Minh không buồn chán Loli đã đố Minh một bài toán sau: Đếm số bộ ba số ~(a, b, c)~ thỏa mãn ~a \times b~, ~a \times c~ và ~b \times c~ đều là một số chính phương với ~1 \le a < b < c \le n~.

Input

• Dòng đầu tiên chứa số nguyên ~T~ - là số test của bài (~1\le T\le 20~).
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~n~ (~1 \le n \le 10^6~).

Output

• ~T~ dòng, mỗi dòng chứa một số nguyên là kết quả số bộ ba (~a, b, c~) thỏa mãn tương ứng với test ở dòng đó.

Sample Input 1

5
10
20
1707
177013
265918

Sample Output 1

1
5
19938
25974765
48116615

Subtask:

• ~20\%~ số điểm có ~T\le 20, n \le 100~.
• ~30\%~ số điểm có ~T\le 20, n \le 10^3~.
• ~20\%~ số điểm có ~T\le 20, n \le 10^5~.
• ~15\%~ số điểm có ~T = 1, n \le 10^6~.
• ~15\%~ số điểm có ~T\le 20, n \le 10^6~.