시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 47 9 8 32.000%

문제

피보나치 수열의 정의는 다음과 같다.

F(0) = F(1) = 1
F(n) = F(n-1) + F(n-2) (n ≥ 2)

n은 피보나치 숫자 F(n)의 인덱스라고 한다.

피보나치의 책 Liber Abaci가 출판된 이후에 많은 사람들은 피보나치 수열에 대해서 많은 연구를 했다. 현재, 많은 성질들이 알려져 있다.

선영이가 코딩보다 좋아하는 것이 바로 피보나치 수를 연구하는 것이다. 피보나치 수에 대한 많은 논문을 읽은 결과 이제 더 이상 밝혀지지 않은 성질은 없다고 생각했다.

그날 밤 이었다. 피보나치가 선영이의 꿈에 나타났다. "멍청하군... 아직 피보나치 수에 대해 중요한 성질이 밝혀지지 않았다고. 예를 들면, 피보나치 숫자 347746739..."

선영이는 잠에서 깨어나 나머지 숫자를 기억하려고 했지만, 기억하지 못했다. 선영이는 피보나치 수에 대한 연구를 계속 하기 위해서 이 숫자를 알아내는 프로그램을 작성하려고 한다.

한 피보나치 숫자의 앞 부분 일부가 주어졌을 때, 이 숫자로 시작하는 피보나치 숫자의 가장 작은 인덱스를 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. (T ≤ 50,000)

각 테스트 케이스는 한 줄로 이루어져 있고, 피보나치 수의 앞 부분 일부가 주어진다. 이 수는 40자리는 넘지 않으며, 불필요한 0이 숫자의 앞에 없다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 숫자로 시작하는 피보나치 수의 가장 작은 인덱스를 출력한다. 만약, 인덱스가 100,000보다 작은 피보나치 숫자 중 그러한 숫자로 시작하는 피보나치 숫자가 없는 경우에는 -1을 출력한다.

예제 입력

15
1
12
123
1234
12345
9
98
987
9876
98765
89
32
51075176167176176176
347746739
5610

예제 출력

Case #1: 0
Case #2: 25
Case #3: 226
Case #4: 1628
Case #5: 49516
Case #6: 15
Case #7: 15
Case #8: 15
Case #9: 43764
Case #10: 49750
Case #11: 10
Case #12: 51
Case #13: -1
Case #14: 1233
Case #15: 22374

힌트