33OJ
登录 注册

#P17699. [ICPC 2019 Nanjing R] A Hard Problem

[ICPC 2019 Nanjing R] A Hard Problem

Problem Description

Given a positive integer nn, you need to find out the minimum integer kk such that for any subset TT of the set {1,2,⋯ ,n}\{1,2,\cdots,n\} of size kk, there exist two different integers u,v∈Tu,v \in T that uu is a factor of vv.

Input Format

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

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

Output Format

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

4
2
3
4
5
2
3
3
4