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
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#undef RUBY
#ifdef RUBY
# Helpful Ruby helper used to find border values used by this algorithm
# Run it with: ruby fibonacci.cpp

	k = 2; p = 0; q = 1; r = 1

	next_pow = 10

	loop do
		if r > next_pow
			puts next_pow, k
			puts
			next_pow *= 10
			exit if next_pow > 10**18
		end
		k+=1
		p, q, r = [q, r, (p+q)]
	end

__END__
#endif

#include <iostream>
#include <string>
#include <math.h>

using namespace std;

const string INVALID("NIE");

typedef unsigned long long F;
typedef pair<F, int> SUFFIX_PAIR;

SUFFIX_PAIR read_suffix()
{
	char input_buff;
	SUFFIX_PAIR retval;
	F suffix = 0;
	int len = 0;

	while (cin >> input_buff)
	{
		if (input_buff >= '0' && input_buff <= '9')
		{
			suffix = suffix * 10 + (input_buff - '0');
			len++;
		}
	}

	return SUFFIX_PAIR(suffix, len);
}

void output(F k)
{
	cout << k;
	exit(0);
}

void special_cases(SUFFIX_PAIR sp)
{
	if (sp.second == 1 && (sp.first == 0 || sp.first == 1))
	{
		output(sp.first);
	}
}

int main(int argc, char **argv)
{
	F k, min_k = 0;
	SUFFIX_PAIR suffix_pair = read_suffix();
	int len = suffix_pair.second;
	F suffix = suffix_pair.first;
	F modulo = pow(10, len);

	special_cases(suffix_pair);

	switch(len)
	{
		case  1:	min_k = 7; break;
		case  2:	min_k = 12; break;
		case  3:	min_k = 17; break;
		case  4:	min_k = 21; break;
		case  5:	min_k = 26; break;
		case  6:	min_k = 31; break;
		case  7:	min_k = 36; break;
		case  8:	min_k = 40; break;
		case  9:	min_k = 45; break;
		case 10:	min_k = 50; break;
		case 11:	min_k = 55; break;
		case 12:	min_k = 60; break;
		case 13:	min_k = 64; break;
		case 14:	min_k = 69; break;
		case 15:	min_k = 74; break;
		case 16:	min_k = 79; break;
		case 17:	min_k = 84; break;
		case 18:	min_k = 88; break;
	}

	F p = 0, q = 1, r = 1, new_r;

	for (k = 2; k < pow(10, len+1) ; k++)
	{
		if (r == suffix && k >= min_k)
		{
			output(k);
		}
		new_r = (q+r) % modulo;
		p = q;
		q = r;
		r = new_r;
	}

	cout << INVALID;
	return 0;
}