Cho dãy vô hạn: ~A = 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5,...~ và số ~n~. Hãy cho biết vị trí thứ ~n~ trong dãy ~A~ là số mấy.

Input:

• Dòng 1: Dòng đầu ghi ~t~ (~t \le 10^6~), là số câu hỏi
• Dòng 2: ~t~ dòng tiếp theo, mỗi dòng ghi ~n~ (~n \le 10^{18}~)

Output:

• Ứng với mỗi câu hỏi, in ra tổng cần tìm

Subtask

• 60% số test: ~t \le 1000;~ ~n \le 10000~
• 40% số test: không có ràng buộc gì thêm

Example

Input

1
6

Output

3

Input

3
2
4
8

Output

1
1
2

Hãy tính tổng: ~S = -1^3 + 2^3 - 3^3 + 4^3 - 5^3 + ...~ gồm ~n~ số hạng.

Input:

• Dòng 1: Dòng đầu ghi ~t~ (~t \le 10^6~), là số câu hỏi
• Dòng 2: ~t~ dòng tiếp theo, mỗi dòng ghi ~n~ (~n \le 2.10^6~)

Output:

• Ứng với mỗi câu hỏi, in ra tổng cần tìm

Subtask

• 40% số test: ~t \le 100;~ ~n \le 1000~
• 30% số test: ~t \le 10000;~ ~n \le 20000~
• 30% số test: không có ràng buộc gì thêm

Example

Input

1
2

Output

7

Input

2
3
5

Output

-20
-81

Cho số ~n~, hãy đếm bộ 3 số ~a, b, c~ (~a \le b \le c~) có tích không vượt quá ~n~.

Input:

• Chứa số nguyên dương ~n~ ~(1 \le ~n~ \le 10^{11})~

Output:

• Yêu cầu bài toán

Subtask

• 40% số test: ~n \le 400~
• 30% số test: ~n \le 10000~
• 30% số test: không có ràng buộc gì thêm

Example

Input

4

Output

5

Explain

Có 5 bộ ba có tích không vượt quá n: (1, 1, 1); (1, 1, 2); (1, 1, 3); (1, 1, 4); (1, 2, 2)