Marisa có một đoạn thẳng độ dài \(P\). Cô muốn cắt nó thành ba đoạn để tạo thành một tam giác vuông. Trong tất cả các tam giác vuông có thể tạo được, hãy tìm diện tích lớn nhất. Nếu không thể tạo tam giác vuông, in ra 0.

Input

• Dòng đầu chứa số nguyên \(T\) — số lượng test (\(1 \le T \le 10^6\)).
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(P\) — độ dài đoạn thẳng (\(1 \le P \le 10^6\)).

Output

• Với mỗi test, in ra diện tích lớn nhất của tam giác vuông có chu vi bằng \(P\). Nếu không tồn tại, in ra 0.

Example

2
12
36

6
54

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(1 \le P \le 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(1 \le P \le 5000\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.