VECTAR13 - Changu Mangu in a Football Team

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 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


Added by:Piyush Kumar
Date:2016-07-16
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:TJU OJ

hide comments
2018-04-24 15:11:21 Luka Jovanoviæ
Nice problem
2018-04-18 12:54:19
How is when n = 3, the answer is 1!!
It should be 3
suppose 1 loses for 2,3
now
1 wins 0, goals 4, conceded 8
2 wins 2, goals 4, coneded 2
3 wins 2 goals 4, conceded 2

now 2 and 3 play
draw in both matches
1 wins 0, goals 4, conceded 8,
2 wins 2, goals 5, conceded 3
3 wins 2, goals 5,conceded 3
2018-04-01 21:13:23
I think this task is bad
2016-07-17 06:56:52
Nice Problem bro ..
2016-07-16 19:04:53 Vipul Srivastava
Yes I agree
2016-07-16 17:54:44 Vipul Srivastava
I think it should be in classical.. gave me a hard time for not thinking it through :(

Re: Thanks, I will keep it here. :) , the only tough part is to comprehend the problem.

Last edit: 2016-07-16 18:23:42
2016-07-16 16:39:13 [Rampage] Blue.Mary
How to calculate the points for a team?

Re: Sorry for the inconvenience, the problem statement has been updated.

Last edit: 2016-07-16 16:51:02
2016-07-16 16:32:33 Vipul Srivastava
Points are awarded based on wins?

Re: The problem statement has been updated. Sorry for the inconvenience.

Last edit: 2016-07-16 16:53:42
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.