A. Try and Cry
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

It's IPL time and you are the owner of Goa Guardians, and you want your team to qualify for playoffs; hence, you are fixing matches. There are $$$N$$$ teams in the tournament, and the first four qualify for playoffs. The tournament is organized in a round robin format, i.e., each team plays with every other team once, and every match results in a win or loss(no draws) and gets $$$1$$$ point for a win and $$$0$$$ point for a loss. If two teams have the same points, then the team with a higher run rate qualifies.

You can decide the outcome of every match and the run rate of every team. Since winning more matches can be suspicious, find the minimum number of wins with which Goa Guardians can qualify, given that you are deciding the outcome of every match of the tournament.

Input

The first line contains a single integer $$$t(1 \le t \le 10^3)$$$ — the number of test cases.

Each test case contains a single integer $$$N (4 \lt N \lt 10^9)$$$ — the number of teams in IPL.

Output

For each test case, print a single integer, the minimum number of wins.

Example
Input
2
5
6
Output
1
1
Note

For the first test case, when there are 5 teams, we can qualify when we win just one match. Consider the following points table:

A - 4 wins

B - 3 wins

C - 2 wins

D - 1 win (Our team of interest)

E - 0 wins

Also, we would not be in the top 4 if we do not win any match. Thus, the optimal answer is 1.