C. Game
time limit per test
2.5 с
memory limit per test
128 МБ
input
standard input
output
standard output

Cody and Tyger want to play a game. Initially, two integers, $$$x$$$ and $$$y$$$ are written on the board. Then, Cody and Tyger take turns, with Cody going first. In each player's turn, they choose two integers on the board such that their absolute difference isn't currently on the board, then add the absolute difference to the board. The player who cannot make a move loses.

Given an integer $$$n$$$, if both Cody and Tyger play optimally, how many games will Cody win across all starting pairs $$$(x, y)$$$ where $$$1 \leq x, y \leq n$$$?

Input

Each test contains multiple testcases. The first line contains the number of testcases $$$t$$$ $$$(1 \leq t \leq 5)$$$.

Each of the next $$$t$$$ lines contain a single integer $$$n$$$ $$$(1 \leq n \leq 10^6)$$$.

Output

For each testcase, output the number of games Cody will win across all starting pairs $$$(x, y)$$$ where $$$1 \leq x, y \leq n$$$, assuming both players play optimally.

Scoring

In tests worth $$$30$$$ points, it is guaranteed that for each testcase $$$1 \leq n \leq 1000$$$.

Example
Input
4
1
2
3
1434
Output
1
2
7
1370142
Note

In the third testcase, Cody wins if the starting pair is $$$(1, 1)$$$, $$$(1, 3)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(3, 1)$$$, $$$(3, 2)$$$, or $$$(3, 3)$$$.

Credit: eggag32