La Chaleur
By Leandro Zatesko 
Brazil
By Leandro Zatesko Brazil
Given a non-negative integer N > 5 represented in the numeral system of some base D1 ≥ 5, a FOURier transform is a choice of another base D2 ≥ 5 to represent N which makes N FOURier, that is, which increases the proportion of digits equal to 4 in the representation of N. For example, N = 411 has 1/3 of the digits equal to 4 in base D1 = 10, but if we change the base to D2 = 11, then, since (411)10 = (344)11, we get 2/3 of the digits equal to 4; so this change is a FOURier transform.
The single line of the input consists only of an integer N (6 ≤ N ≤ 1014).
Print the base D which satisfies 5 ≤ D < N and maximises the proportion of digits equal to 4 in the representation of N. If there are more than one such D, print the largest.
For example, consider N = 6. The only base D which satisfies 5 ≤ D < N is D = 5, for which we have no digits equal to 4 in the representation of N. Hence, the answer is D = 5, since we indeed achieve the maximum proportion of digits equal to 4, even that, in this case, this maximum proportion is actually the null proportion.
| Input Samples | Output Samples |
|
344 |
85 |
|
6 |
5 |
|
411 |
11 |