406971: GYM102638 G Noogies

Because of the extraordinary academic achievements during his university studies, Rudolph Veniaminovich Gotov was the only one to be assigned to work as a math teacher after graduation.

In the class where Rudolph teaches, there are exactly $$$m$$$ students. The math lesson by Rudolph goes as follows. He creates a list of $$$n$$$ ($$$n \geqslant m$$$) problems and distributes it among the students. Then, he calls students to the blackboard using a random number generator. In the first step, the generator generates a number $$$t_1$$$, and then Rudolph calls the first student to the blackboard to solve a problem with number $$$t_1$$$ in the list. In the second step, the generator generates a number $$$t_2$$$, and Rudolph calls the second student to solve the problem number $$$t_2$$$ in the list, and so on, up to the $$$m$$$-th student. The generator is designed so that sequence $$$t_i$$$ is increasing and never exceeds $$$n$$$, i.e., the following inequalities hold: $$$$$$ 1 \leqslant t_1 < t_2 < \cdots < t_m \leqslant n. $$$$$$ If a student can't solve a problem at the blackboard, Rudolf Veniaminovich gives him a noogie.

Rudolf Veniaminovich is already tired of teaching, so his only goal during the lesson is to give each student a noogie.

To do this, he has selected exactly $$$m$$$ complicated problems (which he cannot solve himself) and wants to redesign the random number generator so that it would generate exactly their numbers in the list.

In order not to arouse suspicion, Rudolph came up with the following algorithm for the generator: it receives the number $$$n$$$ as an input (that is, the number of tasks) and generates exactly those numbers that have at least one common divisor with $$$n$$$. Rudolph is sure that such a sequence would look very random. For example, for $$$n=12$$$, such an algorithm would generate numbers $$$2, 3, 4, 6, 8, 9, 10, 12$$$. Having such a "random" generator, Rudolph knows in advance what numbers will be generated, and can put his complicated problems on the right places in the sheet.

However, Rudolph faced a problem — it is not that easy to come up with such a number $$$n$$$ for which the generator would output exactly $$$m$$$ numbers!

Positive integer $$$2 \leqslant m \leqslant 10^8$$$.

Such positive integer $$$n \leqslant 10^{12}$$$ that the generator would generate exactly $$$m$$$ numbers.

8

12

9

21

200

398

It is guaranteed that for any $$$m$$$ in the test cases the desired $$$n$$$ exists.