시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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을 출력한다.

예제 입력 1

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

예제 출력 1

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
W3sicHJvYmxlbV9pZCI6IjYyODYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5YWNcdWJjYTRcdWM5YzAgXHVjNjI0XHViZTBjIFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWM4MTVcdWM3NThcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+RigwKSA9IEYoMSkgPSAxPGJyIFwvPlxyXG5GKG4pID0gRihuLTEpICsgRihuLTIpIChuICZnZTsgMik8XC9wPlxyXG5cclxuPHA+blx1Yzc0MCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjJiXHVjNzkwIEYobilcdWM3NTggXHVjNzc4XHViMzcxXHVjMmE0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4XHVjNzU4IFx1Y2M0NSBMaWJlciBBYmFjaVx1YWMwMCBcdWNkOWNcdWQzMTBcdWI0MWMgXHVjNzc0XHVkNmM0XHVjNWQwIFx1YjljZVx1Yzc0MCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NDAgXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1YzVmNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHViOWNlXHVjNzQwIFx1YzVmMFx1YWQ2Y1x1Yjk3YyBcdWQ1ODhcdWIyZTQuIFx1ZDYwNFx1YzdhYywgXHViOWNlXHVjNzQwIFx1YzEzMVx1YzljOFx1YjRlNFx1Yzc3NCBcdWM1NGNcdWI4MjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgXHVjZjU0XHViNTI5XHViY2Y0XHViMmU0IFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzQgXHViYzE0XHViODVjIFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWI5N2MgXHVjNWYwXHVhZDZjXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHViOWNlXHVjNzQwIFx1YjE3Y1x1YmIzOFx1Yzc0NCBcdWM3N2RcdWM3NDAgXHVhY2IwXHVhY2ZjIFx1Yzc3NFx1YzgxYyBcdWIzNTQgXHVjNzc0XHVjMGMxIFx1YmMxZFx1ZDYwMFx1YzljMFx1YzljMCBcdWM1NGFcdWM3NDAgXHVjMTMxXHVjOWM4XHVjNzQwIFx1YzVjNlx1YjJlNFx1YWNlMCBcdWMwZGRcdWFjMDFcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjBhMCBcdWJjMjQgXHVjNzc0XHVjNWM4XHViMmU0LiBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNThcdWFjMDAgXHVjMTIwXHVjNjAxXHVjNzc0XHVjNzU4IFx1YWZjOFx1YzVkMCBcdWIwOThcdWQwYzBcdWIwYWNcdWIyZTQuICZxdW90O1x1YmE0ZFx1Y2NhZFx1ZDU1OFx1YWQ3MC4uLiBcdWM1NDRcdWM5YzEgXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjOTExXHVjNjk0XHVkNTVjIFx1YzEzMVx1YzljOFx1Yzc3NCBcdWJjMWRcdWQ2MDBcdWM5YzBcdWM5YzAgXHVjNTRhXHVjNTU4XHViMmU0XHVhY2UwLiBcdWM2MDhcdWI5N2MgXHViNGU0XHViYTc0LCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjJiXHVjNzkwIDM0Nzc0NjczOS4uLiZxdW90OzxcL3A+XHJcblxyXG48cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVjN2EwXHVjNWQwXHVjMTFjIFx1YWU2OFx1YzViNFx1YjA5OCBcdWIwOThcdWJhMzhcdWM5YzAgXHVjMjJiXHVjNzkwXHViOTdjIFx1YWUzMFx1YzViNVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1ODhcdWM5YzBcdWI5Y2MsIFx1YWUzMFx1YzViNVx1ZDU1OFx1YzljMCBcdWJhYmJcdWQ1ODhcdWIyZTQuIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM1ZjBcdWFkNmNcdWI5N2MgXHVhY2M0XHVjMThkIFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjNzc0IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM1NGNcdWM1NDRcdWIwYjRcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1YyBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjJiXHVjNzkwXHVjNzU4IFx1YzU1ZSBcdWJkODBcdWJkODQgXHVjNzdjXHViZDgwXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWMyMmJcdWM3OTBcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMmJcdWM3OTBcdWM3NTggXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWM3NzhcdWIzNzFcdWMyYTRcdWI5N2MgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoVCAmbGU7IDUwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4XHVjNzU4IFx1YzU1ZSBcdWJkODBcdWJkODQgXHVjNzdjXHViZDgwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YzIxOFx1YjI5NCA0MFx1Yzc5MFx1YjlhY1x1YjI5NCBcdWIxMThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTcwLCBcdWJkODhcdWQ1NDRcdWM2OTRcdWQ1NWMgMFx1Yzc3NCBcdWMyMmJcdWM3OTBcdWM3NTggXHVjNTVlXHVjNWQwIFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMjJiXHVjNzkwXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4XHVjNzU4IFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVjNzc4XHViMzcxXHVjMmE0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWM3NzhcdWIzNzFcdWMyYTRcdWFjMDAgMTAwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIyYlx1Yzc5MCBcdWM5MTEgXHVhZGY4XHViN2VjXHVkNTVjIFx1YzIyYlx1Yzc5MFx1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI2Mjg2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUmV2ZW5nZSBvZiBGaWJvbmFjY2kiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSB3ZWxsLWtub3duIEZpYm9uYWNjaSBzZXF1ZW5jZSBpcyBkZWZpbmVkIGFzIGZvbGxvd2luZzo8XC9wPlxyXG5cclxuPHA+RigwKSA9IEYoMSkgPSAxPFwvcD5cclxuXHJcbjxwPkYobikgPSBGKG4gLSAxKSArIEYobiAtIDIpICZmb3JhbGw7biAmZ2U7IDI8XC9wPlxyXG5cclxuPHA+SGVyZSB3ZSByZWdhcmQgbiBhcyB0aGUgaW5kZXggb2YgdGhlIEZpYm9uYWNjaSBudW1iZXIgRihuKS48XC9wPlxyXG5cclxuPHA+VGhpcyBzZXF1ZW5jZSBoYXMgYmVlbiBzdHVkaWVkIHNpbmNlIHRoZSBwdWJsaWNhdGlvbiBvZiBGaWJvbmFjY2kmIzM5O3MgYm9vayBMaWJlciBBYmFjaS4gU28gZmFyLCBtYW55IHByb3BlcnRpZXMgb2YgdGhpcyBzZXF1ZW5jZSBoYXZlIGJlZW4gaW50cm9kdWNlZC48XC9wPlxyXG5cclxuPHA+WW91IGhhZCBiZWVuIGludGVyZXN0ZWQgaW4gdGhpcyBzZXF1ZW5jZSwgd2hpbGUgYWZ0ZXIgcmVhZGluZyBsb3RzIG9mIHBhcGVycyBhYm91dCBpdC4gWW91IHRoaW5rIHRoZXJlJnJzcXVvO3Mgbm8gbmVlZCB0byByZXNlYXJjaCBpbiBpdCBhbnltb3JlIGJlY2F1c2Ugb2YgdGhlIGxhY2sgb2YgaXRzIHVucmV2ZWFsZWQgcHJvcGVydGllcy4gWWVzdGVyZGF5LCB5b3UgZGVjaWRlZCB0byBzdHVkeSBzb21lIG90aGVyIHNlcXVlbmNlcyBsaWtlIEx1Y2FzIHNlcXVlbmNlIGluc3RlYWQuPFwvcD5cclxuXHJcbjxwPkZpYm9uYWNjaSBjYW1lIGludG8geW91ciBkcmVhbSBsYXN0IG5pZ2h0LiAmbGRxdW87U3R1cGlkIGh1bWFuIGJlaW5ncy4gTG90cyBvZiBpbXBvcnRhbnQgcHJvcGVydGllcyBvZiBGaWJvbmFjY2kgc2VxdWVuY2UgaGF2ZSBub3QgYmVlbiBzdHVkaWVkIGJ5IGFueW9uZSwgZm9yIGV4YW1wbGUsIGZyb20gdGhlIEZpYm9uYWNjaSBudW1iZXIgMzQ3NzQ2NzM5JmhlbGxpcDsmcmRxdW87PFwvcD5cclxuXHJcbjxwPllvdSB3b2tlIHVwIGFuZCBjb3VsZG4mcnNxdW87dCByZW1lbWJlciB0aGUgd2hvbGUgbnVtYmVyIGV4Y2VwdCB0aGUgZmlyc3QgZmV3IGRpZ2l0cyBGaWJvbmFjY2kgdG9sZCB5b3UuIFlvdSBkZWNpZGVkIHRvIHdyaXRlIGEgcHJvZ3JhbSB0byBmaW5kIHRoaXMgbnVtYmVyIG91dCBpbiBvcmRlciB0byBjb250aW51ZSB5b3VyIHJlc2VhcmNoIG9uIEZpYm9uYWNjaSBzZXF1ZW5jZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZXJlIGFyZSBtdWx0aXBsZSB0ZXN0IGNhc2VzLiBUaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIFQgZGVub3RpbmcgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIChUJmx0Oz01MDAwMCkuPFwvcD5cclxuXHJcbjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgdGhlcmUgaXMgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIG9uZSBub24tZW1wdHkgc3RyaW5nIG1hZGUgdXAgb2YgYXQgbW9zdCA0MCBkaWdpdHMuIEFuZCB0aGVyZSB3b24mcnNxdW87dCBiZSBhbnkgdW5uZWNlc3NhcnkgbGVhZGluZyB6ZXJvZXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgdGhlIHNtYWxsZXN0IGluZGV4IG9mIHRoZSBzbWFsbGVzdCBGaWJvbmFjY2kgbnVtYmVyIHdob3NlIGRlY2ltYWwgbm90YXRpb24gYmVnaW5zIHdpdGggdGhlIGdpdmVuIGRpZ2l0cy4gSWYgbm8gRmlib25hY2NpIG51bWJlciB3aXRoIGluZGV4IHNtYWxsZXIgdGhhbiAxMDAwMDAgc2F0aXNmeSB0aGF0IGNvbmRpdGlvbiwgb3V0cHV0IC0xIGluc3RlYWQgJm5kYXNoOyB5b3UgdGhpbmsgd2hhdCBGaWJvbmFjY2kgd2FudHMgdG8gdG9sZCB5b3UgYmV5b25kcyB5b3VyIGFiaWxpdHkuPFwvcD5cclxuIiwiaGludCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IHRoZSBzbWFsbGVzdCBpbmRleCBvZiB0aGUgc21hbGxlc3QgRmlib25hY2NpIG51bWJlciB3aG9zZSBkZWNpbWFsIG5vdGF0aW9uIGJlZ2lucyB3aXRoIHRoZSBnaXZlbiBkaWdpdHMuIElmIG5vIEZpYm9uYWNjaSBudW1iZXIgd2l0aCBpbmRleCBzbWFsbGVyIHRoYW4gMTAwMDAwIHNhdGlzZnkgdGhhdCBjb25kaXRpb24sIG91dHB1dCAtMSBpbnN0ZWFkICZuZGFzaDsgeW91IHRoaW5rIHdoYXQgRmlib25hY2NpIHdhbnRzIHRvIHRvbGQgeW91IGJleW9uZHMgeW91ciBhYmlsaXR5LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d