Background

Python contestants may try submitting this problem using PyPy3.

Problem Description

The owner of the pizza shop in Lanqiao Town has just baked the $n$-th pizza of his life! To celebrate this important moment, he launched an event called “Lucky Order”, where customers have a chance to win a free pizza. The rules are as follows:

1. Generate the order number: Each customer needs to generate a nine-digit order number. The method is: first, take the digits $1$ to $8$ and arrange them in any order (each digit appears exactly once) to form an eight-digit number. Then, insert one digit from $1$ to $8$ into any position of this eight-digit number (it can be at the beginning, the end, or in the middle), thus obtaining a nine-digit order number.
2. Compute the greatest common divisor to win a free pizza: The owner will compute the greatest common divisor (GCD) of each customer’s order number and $n$. If an order number has the largest GCD with $n$, then that customer has a chance to win a free pizza. Note: the order number must strictly satisfy the generation rules above. If multiple order numbers have the same GCD with $n$ and this value is the maximum, then only the customer whose order number is the smallest in value wins.

Now, Xiaolan also wants to join this event and hopes to win a free pizza. Please help Xiaolan find the order number that allows him to win the free pizza.

Input Format

One line contains an eight-digit positive integer $n$, representing the $n$-th pizza baked by the owner.

Output Format

Output one line containing a nine-digit positive integer, the answer, i.e., the smallest order number with which Xiaolan can win the free pizza.

12345678

415637826

Hint

Constraints

For all testdata, $10^7 \le n < 10^8$.

Translated by ChatGPT 5