eolymp
Competitions

Factorization.

The Magical 3

There's no doubt about it, three is a magical number. Two's company, but three's a crowd, no one ever talks about 2 blind mice, and there are three members in an ACM ICPC team.

Even more magically, almost all integers can be represented as a number that ends in 3 in some numeric base, sometimes in more than one way. Consider the number 11, which is represented as 13 in base 8 and 23 in base 4. For this problem, you will find the smallest base for a given number so that the number's representation in that base ends in 3.

Input

Each line contains one nonnegative integer n. The value n = 0 represents the end of the input and should not be processed. All input integers are less than 231. There are no more than 1000 nonzero values of n.

Output

For each nonzero value of n print on a single line the smallest base for which the number has a representation that ends in 3. If there is no such base, print instead “No such base”.

Time limit 1 second
Memory limit 122.17 MiB
Input example #1
11
123
104
2
3
0
Output example #1
4
4
101
No such base
4
Source 2015 ACM North America - Rocky Mountain, Problem H