{"problem":{"name":"A. Primal Sport","description":{"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. Alice goes first and then they take alternat","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF947A"},"statements":[{"statement_type":"Markdown","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.\n\n## Input\n\nThe 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.\n\n## Output\n\nOutput a single integer — the minimum possible _X_0.\n\n[samples]\n\n## Note\n\nIn 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.","is_translate":false,"language":"English"}],"meta":{"iden":"CF947A","tags":["brute force","math","number theory"],"sample_group":[["14","6"],["20","15"],["8192","8191"]],"created_at":"2026-03-03 11:00:39"}}