{"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":null,"sample_group":[],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}