ANAGCD - Anagrams and GCD

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 AX as the set of all positive integers that are anagrams of X. Note that the set AX contains at least one element: X.

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

You are given the integer N. Your task is to find the minimum element of SN, 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 SN in a single line. If SN is empty, output -1 instead.

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

Example

Input:
12
2023

Output:
48
-1

Added by:Fudan University Problem Setters
Date:2023-03-06
Time limit:1s
Source limit:512B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Based on a Problem from NEERC Moscow Subregional Contest 20XX

hide comments
2023-12-31 22:24:15 [Lakshman]
@Oleg Thanks, Understood.
2023-12-30 00:48:35 Oleg
You can't just take 2 anagrams - you have to take all of them (for some Y) and find gcd of all of them.
ie. gcd(46782, 28476, 84762, 78462,...)
2023-12-29 05:11:33 [Lakshman]
I did not get the 2nd test case
for example [46782 , 28476] are anagram and gcd is 2034.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.