CFPARTY - Party

n people came to a party. Then those, who had no friends among people at the party, left. Then those, who had exactly 1 friend among those who stayed, left as well. Then those, who had exactly 2, 3, ..., n - 1 friends among those who stayed by the moment of their leaving, did the same.

What is the maximum amount of people that could stay at the party in the end?

Input

The first input line contains one number t — amount of tests (1 ≤ t ≤ 105). Each of the following t lines contains one integer number n (1 ≤ n ≤ 105).

Output

For each test output in a separate line one number — the maximum amount of people that could stay in the end.

Example

Input:
1
3

Output:
1

Added by:Efim
Date:2010-08-02
Time limit:0.506s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET
Resource:Codeforces

hide comments
2011-02-26 05:58:29 Ajey Golsangi
Nice problem.
2011-02-13 11:24:18 :D
Giving explanation for such a high N would pretty much give away the solution, and I think you are aware of that! Even giving a solution would be a big hint. I can say that the formula is very simple. It took me way more time to check my solution graph models, than to actually write the program.
2010-11-13 20:02:00 Oshnifg
can someone plz explain me for input 7 ?
2010-09-23 02:09:32 Mitch Schwartz
@ Chandra sekar

i think friendship is a symmetric relation (a~b implies b~a) and the example output is explained when one person is friends with two people who are not friends with each other. nobody leaves on the 0 friends step, two people leave on the 1 friend step, and one person remains.
2010-08-09 06:34:18 pranav
U have 3 people , first 1 guy leaves who has 0 friends so 2 are left in the party, then out of 2 people 1 leaves as he knew the 3rd guy,so we are finally left with 1 guy in the party.I think it should be like this.Now u can say the 2 out of 3 guys could know each other guys can know each other so ...in that case say 1st guy leaves and u r left with 2nd and 3d guy..and if they both know each other both will leave ...leaving 0 guys in the party...which is < 1 as in the previous case as we have been asked to find MAX people remaining...!!

Last edit: 2010-08-09 06:43:03
2010-08-07 13:01:06 Chandra Sekar
Can someone pls explain the example output?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.