Two positive integers (without any leading zeroes) are said to be anagrams of each other if the digits in one integer (in decimal notation) can be rearranged to form the other.

For any positive integer X, define A_X as the set of all positive integers that are anagrams of X. Note that the set A_X contains at least one element: X.

For any positive integer N, define S_N as the set of all positive integers Y, such that the greatest common divisor (GCD) of all integers in A_Y is equal to N.

You are given the integer N. Your task is to find the minimum element of S_N, or report that set is empty.

Input

Several test cases, the number of them is less than 2023. Each test case consists of a single line with a positive integer N without any leading zeroes. The number of digits in N doesn't exceed 1000.

Input terminates by EOF.

Output

For each test case, output the minimum element of S_N in a single line. If S_N is empty, output -1 instead.

Solve this problem by at most 0.5KB of source code.

Example

Input:
12
2023

Output:
48
-1