{"raw_statement":[{"iden":"statement","content":"Alice and Bob begin their day with a quick game. They first choose a starting number _X_0 ≥ 3 and try to reach one million by the process described below.\n\nAlice goes first and then they take alternating turns. In the _i_\\-th turn, the player whose turn it is selects a prime number smaller than the current number, and announces the smallest multiple of this prime number that is not smaller than the current number.\n\nFormally, he or she selects a prime _p_ < _X__i_ - 1 and then finds the minimum _X__i_ ≥ _X__i_ - 1 such that _p_ divides _X__i_. Note that if the selected prime _p_ already divides _X__i_ - 1, then the number does not change.\n\nEve has witnessed the state of the game after two turns. Given _X_2, help her determine what is the smallest possible starting number _X_0. Note that the players don't necessarily play optimally. You should consider all possible game evolutions."},{"iden":"input","content":"The input contains a single integer _X_2 (4 ≤ _X_2 ≤ 106). It is guaranteed that the integer _X_2 is composite, that is, is not prime."},{"iden":"output","content":"Output a single integer — the minimum possible _X_0."},{"iden":"examples","content":"Input\n\n14\n\nOutput\n\n6\n\nInput\n\n20\n\nOutput\n\n15\n\nInput\n\n8192\n\nOutput\n\n8191"},{"iden":"note","content":"In the first test, the smallest possible starting number is _X_0 = 6. One possible course of the game is as follows:\n\n*   Alice picks prime 5 and announces _X_1 = 10\n*   Bob picks prime 7 and announces _X_2 = 14.\n\nIn the second case, let _X_0 = 15.\n\n*   Alice picks prime 2 and announces _X_1 = 16\n*   Bob picks prime 5 and announces _X_2 = 20."}],"translated_statement":[{"iden":"statement","content":"Alice 和 Bob 以一个快速游戏开始他们的一天。他们首先选择一个起始数字 #cf_span[X0 ≥ 3]，并通过以下过程尝试达到一百万。\n\nAlice 先手，然后两人轮流进行。在第 #cf_span[i] 轮中，轮到的玩家选择一个小于当前数字的质数，并宣布不小于当前数字的该质数的最小倍数。\n\n形式上，他或她选择一个质数 #cf_span[p < Xi - 1]，然后找到满足 #cf_span[p] 整除 #cf_span[Xi] 的最小 #cf_span[Xi ≥ Xi - 1]。注意，如果所选质数 #cf_span[p] 已经整除 #cf_span[Xi - 1]，则数字不会改变。\n\nEve 已经见证了游戏进行两轮后的状态。给定 #cf_span[X2]，帮助她确定最小可能的起始数字 #cf_span[X0]。注意，玩家不一定以最优方式玩。你需要考虑所有可能的游戏演变过程。\n\n输入包含一个整数 #cf_span[X2] (#cf_span[4 ≤ X2 ≤ 106])。保证整数 #cf_span[X2] 是合数，即不是质数。\n\n输出一个整数 —— 最小可能的 #cf_span[X0]。"},{"iden":"input","content":"输入包含一个整数 #cf_span[X2] (#cf_span[4 ≤ X2 ≤ 106])。保证整数 #cf_span[X2] 是合数，即不是质数。"},{"iden":"output","content":"输出一个整数 —— 最小可能的 #cf_span[X0]。"},{"iden":"examples","content":"输入\n14\n输出\n6\n\n输入\n20\n输出\n15\n\n输入\n8192\n输出\n8191"},{"iden":"note","content":"在第一个测试中，最小可能的起始数字是 #cf_span[X0 = 6]。一种可能的游戏过程如下：\n\nAlice 选择质数 5 并宣布 #cf_span[X1 = 10]；\nBob 选择质数 7 并宣布 #cf_span[X2 = 14]。\n\n在第二种情况中，设 #cf_span[X0 = 15]：\n\nAlice 选择质数 2 并宣布 #cf_span[X1 = 16]；\nBob 选择质数 5 并宣布 #cf_span[X2 = 20]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ X_0 \\geq 3 $ be the starting integer.  \nLet $ X_1, X_2 \\in \\mathbb{Z} $ be the states after Alice’s and Bob’s moves, respectively.  \n\n**Constraints**  \n1. $ 4 \\leq X_2 \\leq 10^6 $, and $ X_2 $ is composite.  \n2. For $ i \\in \\{1, 2\\} $:  \n   - There exists a prime $ p_i $ such that $ p_i < X_{i-1} $.  \n   - $ X_i = \\min \\{ y \\geq X_{i-1} \\mid p_i \\mid y \\} $.  \n\n**Objective**  \nFind the minimum possible value of $ X_0 $ such that there exist primes $ p_1, p_2 $ and integers $ X_1 $ satisfying the above transition rules and $ X_2 $ is given.","simple_statement":null,"has_page_source":false}