# UVa 10093

## Summary

Given any based number you have to find the minimum base for which that number will be divisible by N-1 in N base.

## Explanation

If this problem is not as easy as its name suggests, then it's not as hard as you may think. You have to find the minimum valid base for that number (maximum digit + 1) and try to divide that number in that base by base-1 to check if divisible until you reach base 62. If it's not divisible by this time then the number is impossible.

The number can be very big to be held in any datatype. So try to divide digit by digit. This problem can be much easier if you know the following formula. Thanks to P.A.Petrov. An N-based number R is divisible by (N-1) if and only if the sum of its digits is divisible by (N-1).

## Gotcha's

No base can be less than 2. There can be negative numbers. Just ignore the sign. Be careful with input "0".

## Input

```3
5
A
+A
-A
Z
+Z
-Z
265
5464
+265
-5464
11111
AAAAA
ABCD
abcd
XYZ
xyz
123456789
987654321
0
1
2
2727
Zz
1010101101
z
41724
123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
123456789ABCDEFGHIJKLMN
```

## Output

```4
6
11
11
11
36
36
36
14
20
14
20
2
11
24
51
52
such number is impossible!
10
10
2
2
3
10
such number is impossible!
2
62
10
62
24
```