Selecting Guard (I)

Author: QuwsarOhi

Problem Setter: Maruf Ahmed Rahad

Intake 35, Department of CSE.

BUBT is a famous university. It’s CSE department is very advanced and they produce good programmers nowadays. They arrange a programming contest every semester. But this time the programmers don’t want to participate in the contest by risking their lives. That’s why Dipu sir set some students to guard the linear street (which is in front of  BUBT) for the programmers’ safety. There are lots of stations in the street.





The students have to guard all the stations and roads between stations. Students can be placed on stations and they guard the roads and stations adjacent to it. But the students are not well behaved. If a road is guarded by multiple students they start fighting. So Dipu sir asked Zabir to write a program that finds the minimum number of students to guard all the stations and roads. Since Zabir is not a good programmer he needs your help. 


In the above figure, if you place a student in station 4, he will guard the two roads connected to station 4 and station 3 and 5 as well.

Input Format

The first line of the input is a single integer T (T<=100) which denotes the number of test cases. Then the next T lines contain a single integer N (N<=100) number of stations of the road.

Output Format

For each test case output in a single line, the minimum number of students needed to guard all the stations and roads.

Samples

Input
2 2 8
Output
1 4
Limits
Language Time Memory
GNU C 11 1s 512MB
GNU C++ 14 1s 512MB
GNU C++ 11 1s 512MB
Statistics
Login To Submit