409238: GYM103466 A A Hard Problem

Given a positive integer $$$n$$$, you need to find out the minimum integer $$$k$$$ such that for any subset $$$T$$$ of the set $$$\{1,2,\cdots,n\}$$$ of size $$$k$$$, there exist two different integers $$$u,v \in T$$$ that $$$u$$$ is a factor of $$$v$$$.

The first line contains an integer $$$T~(1\le T\le 10^5)$$$ indicating the number of test cases.

Each of the following $$$T$$$ lines contains an integer $$$n~(2\le n\le 10^9)$$$ describing a test case.

For each test case, output a line containing an integer which indicates the answer.

4
2
3
4
5

2
3
3
4