← 返回题目列表

Codeforces · 1855/B

B. 最长除数间隔

中文机器翻译题面 查看原题

给定一个正整数 $$$n$$$,找到正整数区间 $$$[l, r]$$$ 的最大大小,使得对于区间中的每个 $$$i$$$(即 $$$l \leq i \leq r$$$),$$$n$$$ 是 $$$i$$$ 的倍数。

给定两个整数 $$$l\le r$$$,区间 $$$[l, r]$$$ 的大小为 $$$r-l+1$$$ (即,它与属于该区间的整数数量一致)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的描述中唯一一行包含一个整数$$$n$$$ ($$$1 \leq n \leq 10^{18}$$$)。

输出

对于每个测试用例,打印一个整数:有效间隔的最大大小。

示例

输入 #1

10
1
40
990990
4204474560
169958913706572972
365988220345828080
387701719537826430
620196883578129853
864802341280805662
1000000000000000000

输出 #1

1
2
3
6
4
22
3
1
2
2

注意

在第一个测试用例中,最大大小的有效区间是 $$$[1, 1]$$$ (它是有效的,因为 $$$n = 1$$$ 是 $$$1$$$ 的倍数),其大小是 $$$1$$$。

在第二个测试用例中,最大大小的有效区间是 $$$[4, 5]$$$ (它是有效的,因为 $$$n = 40$$$ 是 $$$4$$$ 和 $$$5$$$ 的倍数),其大小是 $$$2$$$。

在第三个测试用例中,最大尺寸的有效区间是 $$$[9, 11]$$$。

在第四个测试用例中,最大尺寸的有效区间是 $$$[8, 13]$$$。

在第七个测试用例中,最大尺寸的有效区间为 $$$[327869, 327871]$$$。