躲炮弹

题目描述

小蓝正在玩一个躲炮弹的游戏。游戏中有一个人物和一个炮塔，它们的初始距离为 $n$。

炮塔可能选择在区间 $[L, R]$ 上的任意一个整数 $x$，然后发射的炮弹会飞向小蓝操控的人物。但炮弹只会在飞出 $x$ 的倍数的距离（$x, 2x, 3x, \ldots$）时落地，然后弹回到空中。如果小蓝操控的人物恰好站在了炮弹落地的位置，那么游戏就会结束。

小蓝只能在炮弹发射前移动他的人物，每移动一步，可以使得人物和炮塔的距离增加 $1$ 或者减少 $1$。他想知道最少要移动多少步才能保证自己的人物一定能躲过炮弹。

题目包含T组测试数据,T<=5

输入格式

输入一行包含三个整数 $n, L, R$，相邻的整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数，表示小蓝操纵的人物最少需要移动的步数。

输入输出样例 #1

输入 #1

3
10 2 13
5 10 20
30 8 17

输出 #1

7
0
1

说明/提示

评测用例规模与约定

• 对于 $40\%$ 的评测用例，$n, L, R \leq 10^5$；
• 对于所有评测用例，$1 \leq T \leq 5$，$1 \leq n, L, R \leq 10^8$，$2 \leq L \leq R$。

样例解释

样例：

10 2 13

对样例计算

区间 ([2,13]) 中所有 (x)： 2,3,4,5,6,7,8,9,10,11,12,13

我们要找一个数 (n')，不在任何这些数的倍数中。

从 (n=10) 开始向外找：

10 能被 2,5,10 整除 ❌
11 是质数，不能被 2~13 中任何数整除（除了 11 本身，但 11 也在 [2,13] 吗？是的，(x=11) 是允许的。
检查 (11)：(11/11=1) 整除，危险，所以 ❌

12：能被 2,3,4,6,12 整除 ❌
13：(x=13) 整除 13 ❌
14：能被 2,7,14 整除 ❌
15：能被 3,5,15 ❌
16：能被 2,4,8,16 ❌
17：不能被 [2,13] 任何数整除 ✅ 检验：
17 mod 2=1, mod 3=2, mod 4=1, mod 5=2, mod 6=5, mod 7=3, mod 8=1, mod 9=8, mod 10=7, mod 11=6, mod 12=5, mod 13=4。
所以安全。

17 离 10 差 7 步。

检查有没有更近的：
往前找：9：能被 3,9 ❌
8：能被 2,4,8 ❌
7：能被 7 ❌
6：能被 2,3,6 ❌
5：能被 5 ❌
4：能被 2,4 ❌
3：能被 3 ❌
2：能被 2 ❌
1 不在区间内？但 L=2，x∈[2,13]，1 不是x，所以 1 安全？ 1 离10差9步，但1能被哪些x整除？1/2 不是整数，1/3 不是… 检查 1 mod x 对于 x≥2 永远不为 0，所以 1 是安全的，距离 9 步。比 17 的 7 步大，所以不是最近。

再往前试：
10 不行，11 不行，12 不行，13 不行，14 不行，15 不行，16 不行（16/2=8 整除 2, 16/4=4, 16/8=2, 16/16 但16不在区间内，但 16 mod 2=0 导致危险）。所以16不行。

但前面我们检查过 17 是第一个大于10的可行数吗？大于10的是17，小于10的是… 9不行，8不行，7不行，6不行，5不行，4不行，3不行，2不行，1 可行，但1差9>7，所以17更好。

那 17 差 7 步就是最优的？ 检验一下 n=10 时，从 10 加 7 到 17，减 7 到 3（3 不行），所以只能加 7 步到 17。减9到1可行但更远。

所以最短步数是 7。

因此样例输出 7 就是解释为：
移动 7 步（到 17），对所有 (x\in[2,13]) 安全。