시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB18201281109672.535%

문제

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)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 P가 주어진다. 각 테스트 케이스는 N과 M으로 이루어져 있다. N은 테스트 케이스의 번호이고, M은 문제에서 설명한 m이다.

출력

각 테스트 케이스마다 테스트 케이스 번호를 출력하고 k(M)을 출력한다.

제한

  • 1 ≤ P ≤ 1,000
  • 2 ≤ M ≤ 1,000,000
  • 전체 테스트 케이스에 대해서 k(M)의 합은 500,000 이하

예제 입력 1

5
1 4
2 5
3 11
4 123456
5 987654

예제 출력 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=