/*
De pe infoarena - http://infoarena.ro/problema/fact

Factorial

Se da un numar intreg P. Sa se gaseasca cel mai mic numar natural strict pozitiv N pentru care N! are exact P cifre de 0 la sfarsit.

Se stie ca N! = 1 * 2 * 3 * .... * (N - 1) * N.
Date de intrare

Fisierul fact.in va contine pe prima linie numarul intreg P.
Date de iesire

Pe prima linie a fisierului fact.out se va scrie acel numar N care indeplineste condiitle impuse sau -1 daca nu exista un astfel de N.
Restrictii

    * 0 <= P <= 10^8 < 2^27 - SHOULD BE ENOUGH FOR INT

*/
#include <stdio.h>

#define IN_FILE "fact.in"
#define OUT_FILE "fact.out"

/*
 * O problema mai simplu de rezolvat:
	- Cate cifre de zero are la sfarsit factorialul numarului N?
 * Pornind de la asta, cautare binara pentru N.
 * Se pare ca numarul de biti necesar pentru a stoca un numar va fi intotdeauna mai mic decat numarul de zerouri din factorialul lui !
	- cred ca se poate demonstra prin inductie
 * Ceea ce inseamna ca e suficient sa lucrez cu int !


*** Or sa ma intereseze doar multiplii lui 5 ! (nu si cei ai lui 10)
- La fiecare 5 numere multiple de 5, unul din ele e multiplu de 25.
- La fiecare 25 numere multiple de 5, unul din ele e multiplu de 125.
- La fiecare 125 numere multiple de 5, unul din ele e multiplu de 625.
- ....

2^32 - 1 = 4294967295
13 < log5(4294967295) < 14 
 */
#define MAX_POWER 12
#define MAX_VALUE 1220703125
#define MIN_VALUE 1

int puteri5[MAX_POWER + 1];

void initializeaza_puteri(void)
{
	int i;

	puteri5[0] = 1;
	for (i = 1; i <= MAX_POWER; i++)
		puteri5[i] = 5 * puteri5[i-1];
}

int cati_de_zero(int N)
{
	int i, num_zero = 0;

	for (i = 1; i < MAX_POWER; i++)
		num_zero+= N/puteri5[i];

	return num_zero;
}

int gaseste_N(int P)
{
	int N, min, max, zerouri, gasit = 0;
	/* Cautare binara pentru un N care "are" P zerouri 
	 * Dupa ce am gasit un astfel de N, e usor sa il gasim pe cel mai mic
	 */
	min = MIN_VALUE;
	max = MAX_VALUE;
	while ((min < max) && (gasit == 0))
	{
		N = min/2 + max/2;
		zerouri = cati_de_zero(N);
		if (zerouri == P)
			gasit = 1;
		else if (zerouri > P)
			max = N;
		else
			min = N + 1;
	}

	if (gasit == 0)
		return -1;
	/* returneaza cel mai mic astfel de N */
	return ((N % 10) > 5) ? (N - (N % 10) + 5) : (N - (N % 10));
}

int main(void)
{
	FILE *fin, *fout;
	int i, N, P;

	/* Read input */
	fin = fopen(IN_FILE, "r");
	fscanf(fin, "%d", &P);
	fclose(fin);

	/* Solve this somehow */
	initializeaza_puteri();
	N = gaseste_N(P);


	/* Results */
	fout = fopen(OUT_FILE, "w");
	fprintf(fout, "%d - verificare: %d", N, cati_de_zero(N));
	fclose(fout);

	return 0;
}