Vampire Numbers#3344

Vampire Numbers

1.5 seconds
32 megabytes
Very easy

The number is an interesting number, because 1827 = 21 \times 87, and all of the same digits appear on both sides of the . The number has the same property: 136948 = 146 \times 938.

Such numbers are called Vampire Numbers. More precisely, a number is a Vampire Number if it has a pair of factors, and , where a \times b = v, and together, and have exactly the same digits, in exactly the same quantities, as . None of the numbers , , or can have leading zeros. The mathematical definition states that should have an even number of digits and that and should have the same number of digits, but for the purposes of this problem, we will relax that requirement, and allow and to have differing numbers of digits, and to have any number of digits. Here are some more examples:

126 = 6 \times 21, 10251 = 51 \times 201, 702189 = 9 \times 78021, 29632 = 32 \times 926

Given a number , find the smallest Vampire Number which is greater than or equal to .

Input

There will be several test cases in the input. Each test case will consist of a single line containing a single integer (10 \leq X \leq 1,\!000,\!000). The input will end with a line with a single .

Output

For each test case, output a single integer on its own line, which is the smallest Vampire Number which is greater than or equal to . Output no extra spaces and do not separate answers with blank lines.

Examples

Example 1

Loading
Loading