3128: Mean islanders

Due to the excessive pursuit of $GDP$, the owner of Rainbow Island set up many factories in the island, which led to the pollution of rainbow Island's water source, and the islanders had to go far away to fetch water from $NWU$. 

Islanders often use buckets to carry water, but the evil Rainbow Island island owners in order to drink clean water, even put forward excessive requirements. Rainbow Island has a total of $n$ islanders, each with a bucket, each with a different amount of water because the strength of each islander is different. The island asks the guard to select no more than $x $ buckets at a time, and then divide the amount of water in these buckets equally. 

Obviously, when x is large enough, after a certain number of operations, the amount of water in all buckets will be equal. But what's the minimum $x$? the damned islander wants to know.

Each test contains multiple test cases. The first line contains the number of test cases $T$ ($1 \leq T \leq 1000$). Description of the test cases follows.

The first line of each test case contains one integers integer $n$ ($1 \leq n \leq 10^9$)  — The number of buckets.

For each test, print $x$.

3
4
6
10

2
3
5