INS14D - Digo Needs Guns

no tags 

Digo was given the task to secure a very important room where many famous personalities were residing. So the government provided him with some automated guns which he could fit on the line of intersection between any two walls in the room. The guns can rotate anywhere about the point on the line they are placed, but cannot shoot through walls. Since the country was suffering from financial crisis and automated guns were very expensive, Digo thought of using the minimum number of guns and returning the rest. But Digo did not know the configuration of the room as it was very confidential. He just knew the number of sides the room had. The shape of the room can be any simple polygon. What is the minimum number of guns he must carry with him so it is possible for him to secure every possible polygonic room having n walls.

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 <= 1000000

3 <= n <= 1000000000

Sample:

Input
1
4

Output
1

Note: This question has large I/O files, faster I/O methods are needed to get an AC.


hide comments
shiva890: 2021-10-04 16:11:03

will any one give hint:)

Piyush Kumar: 2016-06-22 15:16:05

There is no need for such a strict TL(for slower languages). If the author's intention was to allow only an O(1) solution, a larger range of N could have been traded for a more lenient TL.

:) : 2014-08-18 09:51:18

cost me 3 WAs for jst the I/O ....

sankar: 2014-04-25 07:27:19

Accepted at first attempt.. My 50th classical :)

Surya kiran: 2014-04-13 20:16:17

Update : The Time limit is increased to 5 seconds and all the submissions are rejudged. Cheers!

Bhavik: 2014-04-04 14:38:19

@psetter: what's the point of making the question so faster i/o dependent?? it reduces the number of users who can get AC having correct logic but getting tle bcoz of just I/O!!!

EDIT: The time limit is now relaxed.

Last edit: 2014-04-13 20:15:29

Added by:Surya Kiran
Date:2014-03-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Insomnia 2014