beecrowd | 3418

# La Chaleur

By Leandro Zatesko Brazil

Timelimit: 3

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.

## Input

The single line of the input consists only of an integer N (6 ≤ N ≤ 1014).

## Output

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