给定一个正整数 $$$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]$$$。