Tuenti Challenge 5

Challenge 1 - The Buffer

If you're a man you may well have heard of an unwritten rule in the men's bathroom. When using the wall-mounted urinals you must always leave a buffer, and this rule may only be broken in an emergency. Under normal circumstances two men should never stand side by side.

We'd like to be able to calculate how many men can use the urinals simultaneously without breaking this rule.

Input

The first line will contain the number of cases.
After that, each line will be the numbers of wall-mounted urinal in a bathroom.

Output

The number of men that can use the urinals simultaneously.

Limits

N = Number of wall-mounted urinals
1 ≤ N ≤ 232 - 1

Sample Input

5
1
2
3
4
5

Sample Output

1
1
2
2
3

Problem stats

Completion time: 10 percentile: 0:13 h
90 percentile: 13:16 h
Submit exec time: min: 5.00 s
10 percentile: 33.00 s
90 percentile: 610.10 s
max: 266189.38 s
Test tries: min: 1
10 percentile: 1
90 percentile: 5
max: 169
# of completions:839