Changu and Mangu are part of a football team which is going to participate in a tournament. In the tournament there are n teams in total. Each team plays twice against every other team (home and away fixture). The team that wins, is awarded 3 points. The team that draws, gets 1 point, while the team that loses gets no points.

At the end of the tournament, the teams are ranked 1 to n according to total points. The rank of each team t having p points is one plus the number of teams having more than p points. It is possible that more than one team have the same ranks.

In addition to the team that has rank 1, the Lucky team is also awarded, if it exists. The Lucky team is the one that has absolutely the highest number of wins (absolutely means no other teams has the same number of wins), absolutely the highest number of goals scored, and absolutely the lowest number of goals conceded, is called the Lucky team. (Lucky Team should have all these properties.)

Changu keeps dreaming about being a part of the Lucky team. Your task is to find out the worst possible rank for the Lucky Team.

Input

The first line contains T, the number of test cases. The next T lines contain a number n, the number of teams participating in the tournament.

Output

For each test case, print on a separate line,  the worst possible rank for the Lucky Team

Example

Input:
2
1
3

Output:
1
1

Constraints:

T <= 10^5

1 <= N <= 10^18