문제
1960년, IBM의 직원 Donald Wall은 피보나치 수열을 m으로 나눈 나머지가 주기를 이룬다는 것을 증명했다.
예를 들어, 피보나치 수열의 처음 10개를 11로 나눈 예는 다음과 같다.
| n |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| F(n) |
1 |
1 |
2 |
3 |
5 |
8 |
13 |
21 |
34 |
55 |
| F(n) mod 11 |
1 |
1 |
2 |
3 |
5 |
8 |
2 |
10 |
1 |
0 |
나머지를 이용해서 만든 수열은 주기가 나타날 수 있다. k(m)을 반복하는 부분 수열의 길이라고 했을 때, k(11) = 10임을 알 수 있다.
Wall은 아래와 같은 여러 가지 성질도 증명했다.
- m > 2인 경우에 k(m)은 짝수이다.
- 임의의 짝수 정수 n > 2에 대해서, k(m) = n인 m이 항상 존재한다.
- k(m) ≤ m2 - 1
- k(2n) = 3×2(n-1)
- k(5n) = 4×5n
- k(2×5n) = 6n
- n > 2라면, k(10n) = 15×10(n-1)
m이 주어졌을 때, k(m)을 구하는 프로그램을 작성하시오.
출력
각 테스트 케이스마다 테스트 케이스 번호를 출력하고 k(M)을 출력한다.
제한
- 1 ≤ P ≤ 1,000
- 2 ≤ M ≤ 1,000,000
- 전체 테스트 케이스에 대해서 k(M)의 합은 500,000 이하
예제 출력 1
1 6
2 20
3 10
4 15456
5 332808
W3sicHJvYmxlbV9pZCI6Ijk0NzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1M2NcdWMwYWNcdWIxNzggXHVjOGZjXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD4xOTYwXHViMTQ0LCBJQk1cdWM3NTggXHVjOWMxXHVjNmQwIERvbmFsZCBXYWxsXHVjNzQwIFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWM1ZjRcdWM3NDQgbVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHVhYzAwIFx1YzhmY1x1YWUzMFx1Yjk3YyBcdWM3NzRcdWI4ZWNcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzk5ZFx1YmE4NVx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWNjOThcdWM3NGMgMTBcdWFjMWNcdWI5N2MgMTFcdWI4NWMgXHViMDk4XHViMjA4IFx1YzYwOFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6NjAlXCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+bjxcL3RoPlxyXG5cdFx0XHQ8dGg+MTxcL3RoPlxyXG5cdFx0XHQ8dGg+MjxcL3RoPlxyXG5cdFx0XHQ8dGg+MzxcL3RoPlxyXG5cdFx0XHQ8dGg+NDxcL3RoPlxyXG5cdFx0XHQ8dGg+NTxcL3RoPlxyXG5cdFx0XHQ8dGg+NjxcL3RoPlxyXG5cdFx0XHQ8dGg+NzxcL3RoPlxyXG5cdFx0XHQ8dGg+ODxcL3RoPlxyXG5cdFx0XHQ8dGg+OTxcL3RoPlxyXG5cdFx0XHQ8dGg+MTA8XC90aD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPkYobik8XC90aD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjI8XC90ZD5cclxuXHRcdFx0PHRkPjM8XC90ZD5cclxuXHRcdFx0PHRkPjU8XC90ZD5cclxuXHRcdFx0PHRkPjg8XC90ZD5cclxuXHRcdFx0PHRkPjEzPFwvdGQ+XHJcblx0XHRcdDx0ZD4yMTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzQ8XC90ZD5cclxuXHRcdFx0PHRkPjU1PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPkYobikgbW9kIDExPFwvdGg+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4yPFwvdGQ+XHJcblx0XHRcdDx0ZD4zPFwvdGQ+XHJcblx0XHRcdDx0ZD41PFwvdGQ+XHJcblx0XHRcdDx0ZD44PFwvdGQ+XHJcblx0XHRcdDx0ZD4yPFwvdGQ+XHJcblx0XHRcdDx0ZD4xMDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+XHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWI5Y2NcdWI0ZTAgXHVjMjE4XHVjNWY0XHVjNzQwIFx1YzhmY1x1YWUzMFx1YWMwMCBcdWIwOThcdWQwYzBcdWIwYTAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gayhtKVx1Yzc0NCBcdWJjMThcdWJjZjVcdWQ1NThcdWIyOTQgXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTg4XHVjNzQ0IFx1YjU0YywgaygxMSkgPSAxMFx1Yzc4NFx1Yzc0NCBcdWM1NGMgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+V2FsbFx1Yzc0MCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzAgXHVjMTMxXHVjOWM4XHViM2M0IFx1Yzk5ZFx1YmE4NVx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5tICZndDsgMlx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDAgayhtKVx1Yzc0MCBcdWM5ZGRcdWMyMThcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWM5ZGRcdWMyMTggXHVjODE1XHVjMjE4IG4gJmd0OyAyXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgayhtKSA9IG5cdWM3NzggbVx1Yzc3NCBcdWQ1NmRcdWMwYzEgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5rKG0pICZsZTsgbTxzdXA+MjxcL3N1cD4gLSAxPFwvbGk+XHJcblx0PGxpPmsoMjxzdXA+bjxcL3N1cD4pID0gMyZ0aW1lczsyPHN1cD4obi0xKTxcL3N1cD48XC9saT5cclxuXHQ8bGk+ayg1PHN1cD5uPFwvc3VwPikgPSA0JnRpbWVzOzU8c3VwPm48XC9zdXA+PFwvbGk+XHJcblx0PGxpPmsoMiZ0aW1lczs1PHN1cD5uPFwvc3VwPikgPSA2bjxcL2xpPlxyXG5cdDxsaT5uICZndDsgMlx1Yjc3Y1x1YmE3NCwgaygxMDxzdXA+bjxcL3N1cD4pID0gMTUmdGltZXM7MTA8c3VwPihuLTEpPFwvc3VwPjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPm1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgayhtKVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggUFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IE5cdWFjZmMgTVx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBOXHVjNzQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHViYzg4XHVkNjM4XHVjNzc0XHVhY2UwLCBNXHVjNzQwIFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWMxMjRcdWJhODVcdWQ1NWMgbVx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAgayhNKVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBQICZsZTsgMSwwMDA8XC9saT5cclxuXHQ8bGk+MiAmbGU7IE0gJmxlOyAxLDAwMCwwMDA8XC9saT5cclxuXHQ8bGk+XHVjODA0XHVjY2I0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIGsoTSlcdWM3NTggXHVkNTY5XHVjNzQwIDUwMCwwMDAgXHVjNzc0XHVkNTU4PFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiI5NDcxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUGlzYW5vIFBlcmlvZHMiLCJkZXNjcmlwdGlvbiI6IjxwPklOIDE5NjAsIERvbmFsZCBXYWxsIG9mIElCTSwgaW4gV2hpdGUgUGxhaW5zLCBOWSwgcHJvdmVkIHRoYXQgdGhlIHNlcmllcyBvYnRhaW5lZCBieSB0YWtpbmcgZWFjaCBlbGVtZW50IG9mIHRoZSBGaWJvbmFjY2kgc2VyaWVzIG1vZHVsbyBtIHdhcyBwZXJpb2RpYy48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIHRoZSBmaXJzdCB0ZW4gZWxlbWVudCBvZiB0aGUgRmlib25hY2NpIHNlcXVlbmNlLCBhcyB3ZWxsIGFzIHRoZWlyIHJlbWFpbmRlcnMgbW9kdWxvIDExLCBhcmU6PFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDo2MCVcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5uPFwvdGg+XHJcblx0XHRcdDx0aD4xPFwvdGg+XHJcblx0XHRcdDx0aD4yPFwvdGg+XHJcblx0XHRcdDx0aD4zPFwvdGg+XHJcblx0XHRcdDx0aD40PFwvdGg+XHJcblx0XHRcdDx0aD41PFwvdGg+XHJcblx0XHRcdDx0aD42PFwvdGg+XHJcblx0XHRcdDx0aD43PFwvdGg+XHJcblx0XHRcdDx0aD44PFwvdGg+XHJcblx0XHRcdDx0aD45PFwvdGg+XHJcblx0XHRcdDx0aD4xMDxcL3RoPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGhlYWQ+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+RihuKTxcL3RoPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MjxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzxcL3RkPlxyXG5cdFx0XHQ8dGQ+NTxcL3RkPlxyXG5cdFx0XHQ8dGQ+ODxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTM8XC90ZD5cclxuXHRcdFx0PHRkPjIxPFwvdGQ+XHJcblx0XHRcdDx0ZD4zNDxcL3RkPlxyXG5cdFx0XHQ8dGQ+NTU8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+RihuKSBtb2QgMTE8XC90aD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjI8XC90ZD5cclxuXHRcdFx0PHRkPjM8XC90ZD5cclxuXHRcdFx0PHRkPjU8XC90ZD5cclxuXHRcdFx0PHRkPjg8XC90ZD5cclxuXHRcdFx0PHRkPjI8XC90ZD5cclxuXHRcdFx0PHRkPjEwPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4wPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5UaGUgc2VxdWVuY2UgbWFkZSB1cCBvZiB0aGUgcmVtYWluZGVycyB0aGVuIHJlcGVhdHMuIExldCBrKG0pIGJlIHRoZSBsZW5ndGggb2YgdGhlIHJlcGVhdGluZyBzdWJzZXF1ZW5jZTsgaW4gdGhpcyBleGFtcGxlLCB3ZSBzZWUgaygxMSkgPSAxMC48XC9wPlxyXG5cclxuPHA+V2FsbCBwcm92ZWQgc2V2ZXJhbCBvdGhlciBwcm9wZXJ0aWVzLCBzb21lIG9mIHdoaWNoIHlvdSBtYXkgZmluZCBpbnRlcmVzdGluZzo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5JZiBtICZndDsgMiwgayhtKSBpcyBldmVuLjxcL2xpPlxyXG5cdDxsaT5Gb3IgYW55IGV2ZW4gaW50ZWdlciZuYnNwO24gJmd0OyAyLCB0aGVyZSBleGlzdHMgbSBzdWNoIHRoYXQmbmJzcDtrKG0pID0gbi48XC9saT5cclxuXHQ8bGk+ayhtKSAmbGU7IG08c3VwPjI8XC9zdXA+Jm5ic3A7LSAxPFwvbGk+XHJcblx0PGxpPmsoMjxzdXA+bjxcL3N1cD4pID0gMyZ0aW1lczsyPHN1cD4obi0xKTxcL3N1cD48XC9saT5cclxuXHQ8bGk+ayg1PHN1cD5uPFwvc3VwPikgPSA0JnRpbWVzOzU8c3VwPm48XC9zdXA+PFwvbGk+XHJcblx0PGxpPmsoMiZ0aW1lczs1PHN1cD5uPFwvc3VwPikgPSA2bjxcL2xpPlxyXG5cdDxsaT5JZiBuICZndDsgMiwgaygxMDxzdXA+bjxcL3N1cD4pID0gMTUmdGltZXM7MTA8c3VwPihuLTEpPFwvc3VwPjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkZvciB0aGlzIHByb2JsZW0sIHlvdSBtdXN0IHdyaXRlIGEgcHJvZ3JhbSB0aGF0IGNhbGN1bGF0ZXMgdGhlIGxlbmd0aCBvZiB0aGUgcmVwZWF0aW5nIHN1YnNlcXVlbmNlLCBrKG0pLCBmb3IgZGlmZmVyZW50IG1vZHVsbyB2YWx1ZXMgbS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgUCwmbmJzcDt3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGRhdGEgc2V0cyB0aGF0IGZvbGxvdy4gRWFjaCBkYXRhIHNldCBpcyBhIHNpbmdsZSBsaW5lIHRoYXQgY29uc2lzdHMgb2YgdHdvIHNwYWNlIHNlcGFyYXRlZCBpbnRlZ2VyIHZhbHVlcyBOIGFuZCBNLiBOIGlzIHRoZSBkYXRhIHNldCBudW1iZXIuIE0gaXMgdGhlIG1vZHVsbyB2YWx1ZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCB0aGVyZSBpcyBvbmUgbGluZSBvZiBvdXRwdXQuIEl0IGNvbnRhaW5zIHRoYSBkYXRhIHNldCBudW1iZXIgKE4pIGZvbGxvd2VkIGJ5IGEgc2luZ2xlIHNwYWNlLCBmb2xsb3dlZCBieSB0aGUgbGVuZ3RoIG9mIHRoZSByZXBlYXRpbmcgc3Vic2VxdWVuY2UgZm9yIE0sIGsoTSkuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgUCAmbGU7IDEsMDAwPFwvbGk+XHJcblx0PGxpPjIgJmxlOyBNICZsZTsgMSwwMDAsMDAwPFwvbGk+XHJcblx0PGxpPlRoZSBzdW0gb2YgayhNKSZyc3F1bztzIGluIGFsbCB0ZXN0IGNhc2VzIGluIGEgc2luZ2xlIHRlc3QgZmlsZSBpcyBhdCBtb3N0IDUwMCwwMDAuPFwvbGk+XHJcbjxcL3VsPlxyXG4ifV0=