Packaging Cupcakes

Problem statement

A bakery has N cupcakes ready for a delivery and must choose one box capacity for the whole batch. It fills as many complete boxes as possible, placing exactly the chosen number of cupcakes in each box. Cupcakes that cannot fill another complete box stay at the counter. The baker wants to choose the capacity that leaves the largest possible number at the counter. Your task Choose an integer box capacity K between 1 and N, inclusive, that maximizes N modulo K. Output the capacity K, not the number of cupcakes left over. If several capacities give the same maximum, output the largest of them. Important details All boxes use the same capacity, and partially filled boxes are not dispatched. A capacity that divides N leaves no cupcakes. For N = 1 the only permitted capacity is 1. Each batch is considered separately. Worked example For N = 9, choosing K = 5 fills one box and leaves 4 cupcakes. Capacities 1 through 4 leave at most 1 cupcake, while capacities 6 through 9 leave at most 3. Therefore the answer is 5. For N = 1, output 1.

Input format

The first line contains T. Each of the next T lines contains one integer N.

Output format

For each batch, print the box capacity that maximizes the leftover count.

Constraints

1 <= T <= 1000; 1 <= N <= 100000000.

Sample input

2
9
1

Sample output

5
1