CODGRF - Deconnecting

We define a Beta graph as a set of nodes connected by edges such that one node is connected to another node by at most one edge and no node has an edge starting and ending on itself. Each node has a finite number called 'degree' associated with it which is the number of edges connecting that node to the rest of the nodes.

There are n nodes in a given Beta graph. Those nodes with degree=0 are removed from the graph. Then those, who had degree=1 were removed (and so are the edges connecting that node to the rest of the nodes). Then those, who had degree equal to 2, 3 ... n-1 were removed (including their edges).

For any Beta graph with n nodes find the maximum number of nodes that can remain after the above procedure is completed.

Input

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

Output

For each test case output in a separate line the maximum number of nodes that can remain after the above procedure is completed.

Example

Input:
1
3

Output:
1

Added by:CSI
Date:2013-09-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2017-09-18 21:57:07
It is EXTREMELY easy.
2014-03-20 05:02:57 [Lakshman]
All problem by CSI are copy of other problems on SPOJ.
@CSI Please do not upload duplicate problems.
2014-03-17 15:02:25 Bhavik
easy if you get the logic:)
@csi:there is similar problem like this but with completely different statement, though I don't remember the problem name!!:)

Last edit: 2014-03-17 15:18:29
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.