Cho một bảng vô hạn, các hàng được đánh số trên xuống dưới bắt đầu từ \(0\), các cột được đánh số từ trái sáng phải bắt đầu từ \(0\). Bảng được đánh dấu như sau:

• Ở hàng \(0\), không có ô nào được đánh dấu.
• Ở hàng \(1\), ô đầu tiên không được đánh dấu, ô tiếp theo được đánh dấu, ô tiếp theo nữa không được đánh dấu, ô tiếp theo nữa nữa được đánh dấu, và cứ như thế.
• Ở hàng \(2\), \(2\) ô đầu tiên không được đánh dấu, \(2\) ô tiếp theo được đánh dấu, và cứ tiếp tục luân phiên như vậy.
• Như vậy, ở hàng thứ \(i\) sẽ có \(i\) ô đầu tiên không được đánh dấu, \(i\) ô tiếp theo được đánh dấu, và cứ tiếp tục luân phiên như vậy.

Yêu cầu: Đếm số lượng ô được đánh dấu ở cột thứ \(k\), có thể chứng minh được rằng số lượng ô được đánh dấu ở một cột nào đó là hữu hạn.

Input

• Dòng đầu tiên chứa một số nguyên \(t\) \((1 \leq t \leq 1000)\) \(-\) số lượng test case.
• \(t\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(k\) \((0 \leq k \leq 10^9)\) \(-\) chỉ số của cột cần đếm số ô được đánh dấu.

Output

• In ra \(t\) dòng, mỗi dòng in ra một số nguyên là số lượng ô được đánh dấu ứng với testcase đó.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(t \leq 100, \ k \leq 1000\).
• Subtask \(2\) (\(40\%\) số điểm): \(t \leq 100, \ k \leq 10^5\).
• Subtask \(3\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

5
0
1
2
3
4

Output

0
1
1
3
2

Note

Hình dưới đây là một phần đầu của bảng vô hạn (ô màu đen là ô được đánh dấu):