Factorial

Problem Description

You task is to find minimal natural number N, so that N! contains exactly Q zeroes on the trail in decimal notation. As you know N! = 12…*N. For example, 5! = 120, 120 contains one zero on the trail.

Input

One number Q written in the input (0<=Q<=10^8).

Output

Write “No solution”, if there is no such number N, and N otherwise.

Sample test(s)

Input

2

Output

10

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>

int main() {
std::ios::sync_with_stdio(false);

int q;
std::cin >> q;

if(q == 0) {
std::cout << 1 << std::endl;
}

long long left = 5;
long long right = 5 * q;
long long res = -1;
while(left <= right) {
long long mid = (left + right) / 2;
long long tmpMid = mid;
int count = 0;
while(tmpMid != 0) {
tmpMid /= 5;
count += tmpMid;
}
if(count == q) {
res = mid;
right = mid - 1;
} else if(count > q) {
right = mid - 1;
} else {
left = mid + 1;
}
}

if(res == -1) {
std::cout << "No solution" << std::endl;
} else {
std::cout << res << std::endl;
}

return 0;
}