33OJ
登录 注册

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

[ICPC 2019 Nanjing R] A Hard Problem

题目描述

给定一个正整数 nn,你需要找出最小的整数 kk,使得对于集合 {1,2,⋯ ,n}\{1,2,\cdots,n\} 的任意一个大小为 kk 的子集 TT,总存在两个不同的整数 u,v∈Tu, v \in T,满足 uu 是 vv 的因子。

输入格式

第一行包含一个整数 T (1≤T≤105)T~(1\le T\le 10^5),表示测试数据的组数。

接下来的 TT 行,每行包含一个整数 n (2≤n≤109)n~(2\le n\le 10^9),描述一组测试数据。

输出格式

对于每组测试数据,输出一行一个整数,表示对应的答案。

4
2
3
4
5
2
3
3
4

提示

翻译由 DeepSeek V4 Pro 完成