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