【问题描述】
lzh养了n头猪，每头猪有一个编号,它们的编号从1到n，第i头猪的编号为i。研究发现lzh养的猪有一种奇怪的习性，只有当两只猪的编号同时大于等于2且不互质的时候（两个数不互质表示这两个数有一个除1以外的公因子），它们才会一起玩游戏。编号为1的猪比较可爱，所以它和所有的猪都可以一起玩游戏。现在机器人lzh想要从n头猪中任意选出k头（至少选出两头）,保证其中至少有两只会一起玩游戏，他想要找到最小的k值，聪明的你能帮帮它吗？
【输入形式】
第一行输入一个正整数，表示有T组测试样例接下来的T行中，每一行有一个正整数表示无尾象的总数。保证n>=2且n<=1000且T<=100。
【输出形式】
对于每组样例输出一个最小的k。
【样例输入】
3
2
3
10
【样例输出】
2
3
5
【样例说明】对于第二组样例如果只选择两头，那么当你选到编号位2和3的大象时，不满足条件，而当你选择三头时一定满足，所以至少选出三头。
对于第三组样例如果只选择四头，那么当你选到编号为2，3，5，7的四头大象时，不满足条件，而选择而当你选择五头是一定满足，所以至少选出五头。
【时间和空间限制】
时间限制：1s
空间限制：256MB
| 难度等级： | 0 |
| 总通过次数： | 107 |
| 总提交次数： | 189 |