SPOJ Brasil

Joker has planned a bank robbery again. But this time Gordon has got to know about it! Since batman is tired and is on a vacation, So he himself wants to catch the joker (which is impossible!) For that, he has planned to put cameras with automatic guns inside the bank. The bank is peculiar in shape. It is that of an irregular closed polygon with N sides. The cameras can be fitted ONLY at the corners (INTERSECTION of the walls and are rotatable along vertical axis). That means the camera guns can rotate horizontally from one wall of the corner to another covering the area between the walls. It can detect any movement within that area until infinite distance and will shoot whenever it detects a movement. Assuming that the robbery is going to take place at night when there is no bankers or clients but only robbers, find the minimum number of guns Gordon needs to place to kill the joker and his robbers.

Input

The first line consists of a single integer T denoting the number of test cases. T lines follow each containing an integer N denoting the number of sides.

Output

For each test case print the required answer.

Constraints

1 ≤ T ≤ 1000

3 ≤ n ≤ 100000

Example

Input:
1
8

Output:
2