Giáo sư X dự định đào một cái hồ trong khuôn viên cơ sở nghiên cứu của mình để có thể đi dạo quanh hồ trong lúc tư duy giải quyết các vấn đề thách thức của nhân loại. Ông có sở thích đặc biệt với các hình tam giác vuông và dựa trên những ước lượng về độ dài bước chân cũng như thời gian đi dạo. Ông muốn đào một cái hồ thỏa mãn tất cả các yêu cầu sau:

• Mặt hồ có dạng hình tam giác vuông với ba cạnh đều là số nguyên dương

• Chu vi của hồ đúng bằng một số nguyên ~p~ cho trước

• Nếu có nhiều thiết kế hồ thỏa mãn cả hai yêu cầu trên, ông muốn chọn một thiết kế có diện tích mặt hồ lớn nhất có thể.

Yêu cầu: Cho biết diện tích mặt hồ mà giáo sư X có thể xây được theo các yêu cầu đã cho.

Input

• Dòng 1 chứa số nguyên dương ~T \le 10^5~ là số test

• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~p \le 10^6~ ứng với một test

Output

Ghi ra ~T~ dòng, mỗi dòng ghi kết quả một test là một số nguyên duy nhất là diện tích mặt hồ mà giáo sư X có thể xây được. Nếu không thể xây được hồ thỏa mãn yêu cầu đề ra, ghi ra số 0. (Có thể chứng minh được rằng mọi tam giác vuông có ba cạnh là số nguyên dương thì diện tích của nó luôn là số nguyên)

Scoring

Sample Input 1

6
12
36
112
3344
888888
20

Sample Output 1

6
54
336
476520
33879966120
0

Notes

Về cách chọn ~3~ cạnh của tam giác vuông:

• Test 1: ~12 = 3 + 4 + 5~

• Test 2: ~36 = 9 + 12 + 15~

• Test 3: ~112 = 14 + 48 + 50~

• Test 4: ~3344 = 912 + 1045 + 1387~

• Test 5: ~888888 = 256410 + 264264 + 368214~

• Test 6: Không có tam giác vuông có độ dài cạnh nguyên mà chu vi bằng ~20~