{"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[Xi]。注意，如果所选质数 #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, X_1, X_2 \\in \\mathbb{Z} $ be the state of the game after 0, 1, and 2 turns, respectively.  \nLet $ \\mathbb{P} $ denote the set of prime numbers.\n\n**Constraints**  \n1. $ X_2 \\in \\mathbb{Z} $, $ 4 \\leq X_2 \\leq 10^6 $, and $ X_2 $ is composite.  \n2. $ X_0 \\geq 3 $.  \n3. For $ i \\in \\{1, 2\\} $:  \n   - There exists a prime $ p_i < X_{i-1} $ such that  \n     $$\n     X_i = \\min \\{ m \\geq X_{i-1} \\mid p_i \\mid m \\}\n     $$\n   - Equivalently, $ X_i = \\left\\lceil \\frac{X_{i-1}}{p_i} \\right\\rceil \\cdot p_i $\n\n**Objective**  \nFind the minimum possible value of $ X_0 $ such that there exist primes $ p_1, p_2 $ with $ p_1 < X_0 $, $ p_2 < X_1 $, and the above recurrence yields the given $ X_2 $.","simple_statement":null,"has_page_source":false}