Distantland#3073

Distantland

1 секунда
64 мегабајта
Врло тешко

In the Republic of Distantland, people celebrate their independence day every year. However, since it happened a very long time ago, nobody remembers the exact date. The only thing known is that today, the number of days elapsed since their independence () is a perfect square, and it is the largest possible number that can be written as the product of distinct numbers less than or equal to .

Since a year in Distantland has days, the citizens only need to find modulo . Note that they are interested in the largest , not the largest modulo .

Улаз

Each test case is described by a single line containing an integer (1 \leq n \leq 10000000). The input ends with a line containing .

Излаз

For each test case, output the number of days since the Republic became independent, modulo , one per line.

Примери

Пример 1

Loading
Loading