For integers
b ( b >= 2 ) and
n ( n >= 1 ) let the function
f(b, n) be defined as follows:
\(f (b, n) = n when\ n < b \\
f (b, n) = f (b, floor (n / b)) + (n \ mod \ b) when \ n >= b\)
Here
floor(n / b) denotes the largest integer not greater than
n / b;
n mod b denotes the remainder of
n divided by
b.
Less formally,
f(b, n) is equal to the sum of the
n digits in base
b. For example, the following is true:
\(f (10.87654) = 8 + 7 + 6 + 5 + 4 = 30\\
f (100.87654) = 8 + 76 + 54 = 138\)
You are given the integers
n and
s. Determine if there is an integer
b (b >= 2) such that
f(b, n) = s. If the answer is yes, find the smallest of these
b.
Input
The first line contains an integer
n (1 <= n <= 10
11). The second line contains an integer
s (1 <= s <= 10
11).
Imprint
Output the answer to the problem. If there is no answer, then print
-1.
Examples
| # |
Input |
Output |
| 1 |
87654
30 |
10 |
| 2 |
87654
138 |
100 |
| 3 |
87654
45678 |
-1 |
| 4 |
31415926535
1 |
31415926535 |
| 5 |
1
31415926535 |
-1 |