Alice 和 Bob 以一场快速游戏开始他们的一天。他们首先选择一个起始数字 X0 ≥ 3,并尝试通过下面描述的过程达到 100 万。
Alice 先走,然后他们交替轮流。在第i回合中,轮到的玩家选择一个小于当前数字的素数,并宣布该素数的不小于当前数字的最小倍数。
正式地,他或她选择一个素数 p < Xi - 1,然后找到最小的 Xi ≥ Xi - 1,使得 p 除 Xi。请注意,如果所选素数 p 已整除 Xi - 1,则该数字不会改变。
Eve在两回合后见证了游戏的状态。给定 X2,帮助她确定最小的可能起始数 X0。请注意,玩家不一定会发挥最佳状态。您应该考虑所有可能的游戏演变。
输入
输入包含单个整数 X2 (4 ≤ X2 ≤ 106)。保证整数X2是合数,即不是素数。
输出
输出一个整数——可能的最小 X0。
示例
输入 #1
14
输出 #1
6
输入 #2
20
输出 #2
15
输入 #3
8192
输出 #3
8191
注意
在第一个测试中,最小可能的起始数字是 X0 = 6。游戏的一个可能的过程如下:
- Alice 选择素数 5 并宣布 X1 = 10
- Bob 选择素数 7 并宣布 X2 = 14。
在第二种情况下,令 X0 = 15。
- Alice 选择素数 2 并宣布 X1 = 16
- Bob 选择素数 5 并宣布 X2 = 20。