问题 E: Chess
内存限制：256 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：1
通过：1
题目描述
LNC 喜欢所有k 进制下所有数位的乘积为自身因子的数.他称之为LNC数.
例如: 当k=10时,y=(36)10 是 LNC 数, 因为 (3×6)|36.
当k=4时,y=(12)4 是 LNC 数, 因为转换成十进制后(12)4=(6)10, 而 (1×2)|6.
当k=2时,y=(1101)2 不是 LNC 数, 因为转换成十进制后(1101)2 =(13)10, 而 0 不是 13 的因子.
LNC 在和 LJJ 玩一个游戏, LJJ 给出 x 枚棋子, 然后LNC 选定一个整数k (k≥2). 随后他们交替取走 若干枚棋子, 要求取走的棋子数量是k 进制意义下的LNC数.LNC先手,先取完的获胜.两个人都绝顶 聪明, 故都会选择最优的策略.
LJJ 觉得这个游戏很不公平,他们一共玩了T 局游戏,对于每局游戏他给出的x,他希望知道最小的k使 得LNC先手必胜.
例如: 当k=10时,y=(36)10 是 LNC 数, 因为 (3×6)|36.
当k=4时,y=(12)4 是 LNC 数, 因为转换成十进制后(12)4=(6)10, 而 (1×2)|6.
当k=2时,y=(1101)2 不是 LNC 数, 因为转换成十进制后(1101)2 =(13)10, 而 0 不是 13 的因子.
LNC 在和 LJJ 玩一个游戏, LJJ 给出 x 枚棋子, 然后LNC 选定一个整数k (k≥2). 随后他们交替取走 若干枚棋子, 要求取走的棋子数量是k 进制意义下的LNC数.LNC先手,先取完的获胜.两个人都绝顶 聪明, 故都会选择最优的策略.
LJJ 觉得这个游戏很不公平,他们一共玩了T 局游戏,对于每局游戏他给出的x,他希望知道最小的k使 得LNC先手必胜.
输入格式
输入第一行一个正整数T (1≤T ≤1×102),表示数据组数.
接下来T 行每行一个正整数x(3≤x≤1018),表示LJJ给出的数x.
接下来T 行每行一个正整数x(3≤x≤1018),表示LJJ给出的数x.
输出格式
输出T 行每行一个正整数k,表示每个询问的最小的k,使LNC先手必胜
输入样例 复制
3
9
5
10
输出样例 复制
2
2
3
数据范围与提示
当x=5的时候,LNC可以选择k=2.x=(5)10=(101)2.
LNC 先手拿掉(11)2, 此时 x=(10)2, LJJ 只能拿走 (1)2, LNC 拿走最后的 (1)2 获胜.
又因为k=2已经不能再小了,所以最终答案为k=2
LNC 先手拿掉(11)2, 此时 x=(10)2, LJJ 只能拿走 (1)2, LNC 拿走最后的 (1)2 获胜.
又因为k=2已经不能再小了,所以最终答案为k=2