GCD - Greatest Common Divisor

no tags 

Consider the decimal representation of a natural number N.
Find the greatest common divisor (GCD) of all numbers that can be obtained by permuting the digits in the given number. Leading zeroes are allowed.

Input

Every line of input contains an integer, representing the original number N(0 < N < 10^250).

Output

For every test case, print the GCD of all numbers, which can be obtained from the given one by permuting the digits.

Score

Score is the length of your source.

Example

Input:
21
3
Output:
3
3

hide comments
alexbandeira: 2015-10-05 17:15:34

input is a file EOF? :(

HWK: 2011-07-17 03:56:07

Could you give some more difficult examples?
Edit: It isn't necessary anymore. :-)

Last edit: 2011-06-08 14:29:44
Vivek Anand: 2011-07-17 03:56:07

idea is simple:) implementation is difficult:( lol

Last edit: 2010-09-16 04:07:10

Added by:Bin Jin
Date:2007-07-27
Time limit:1s
Source limit:2000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:from an ACM/ICPC regional contest