GDGALKN - GORDON AND GALLERY

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 camera's 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

Added by:hulk
Date:2016-04-01
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY

hide comments
2017-12-12 00:24:27
Cameras are rotatable along vertical axis and guns along horizontal axis.
Is that so ?
2017-07-28 15:42:46
Easy. If You can't figure it out by reading, try going for pen and paper :)
2016-09-08 16:15:13
What is the logic for this problem , please reply.
2016-05-06 08:00:36
it's there any specific format to show the answer?

EDIT : please follow the given I/O format


Last edit: 2016-05-18 23:06:16
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.