시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 252 188 163 80.296%

문제

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 (1 ≤ P ≤ 1000)가 주어진다. 각 테스트 케이스는 N과 M으로 이루어져 있다. N은 테스트 케이스의 번호이고, M은 문제에서 설명한 m이다. (2 ≤ M ≤ 1,000,000)

출력

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

예제 입력 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+V2FsbFx1Yzc0MCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YzVlY1x1YjdlY1x1YWMwMFx1YzljMCBcdWMxMzFcdWM5YzhcdWIzYzQgXHVjOTlkXHViYTg1XHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm0gJmd0OyAyXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMCBrKG0pXHVjNzQwIFx1YzlkZFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNzg0XHVjNzU4XHVjNzU4IFx1YzlkZFx1YzIxOCBcdWM4MTVcdWMyMTggbiAmZ3Q7IDJcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBrKG0pID0gblx1Yzc3OCBtXHVjNzc0IFx1ZDU2ZFx1YzBjMSBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPmsobSkgJmxlOyBtPHN1cD4yPFwvc3VwPiAtIDE8XC9saT5cclxuXHQ8bGk+aygyPHN1cD5uPFwvc3VwPikgPSAzJnRpbWVzOzI8c3VwPihuLTEpPFwvc3VwPjxcL2xpPlxyXG5cdDxsaT5rKDU8c3VwPm48XC9zdXA+KSA9IDQmdGltZXM7NTxzdXA+bjxcL3N1cD48XC9saT5cclxuXHQ8bGk+aygyJnRpbWVzOzU8c3VwPm48XC9zdXA+KSA9IDZuPFwvbGk+XHJcblx0PGxpPm4gJmd0OyAyXHViNzdjXHViYTc0LCBrKDEwPHN1cD5uPFwvc3VwPikgPSAxNSZ0aW1lczsxMDxzdXA+KG4tMSk8XC9zdXA+PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+bVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBrKG0pXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBQICgxICZsZTsgUCAmbGU7IDEwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgTlx1YWNmYyBNXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIE5cdWM3NDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWM3NzRcdWFjZTAsIE1cdWM3NDAgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YzEyNFx1YmE4NVx1ZDU1YyBtXHVjNzc0XHViMmU0LiAoMiAmbGU7IE0gJmxlOyAxLDAwMCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwIGsoTSlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijk0NzEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQaXNhbm8gUGVyaW9kcyIsImRlc2NyaXB0aW9uIjoiPHA+SU4gMTk2MCwgRG9uYWxkIFdhbGwgb2YgSUJNLCBpbiBXaGl0ZSBQbGFpbnMsIE5ZLCBwcm92ZWQgdGhhdCB0aGUgc2VyaWVzIG9idGFpbmVkIGJ5IHRha2luZyBlYWNoIGVsZW1lbnQgb2YgdGhlIEZpYm9uYWNjaSBzZXJpZXMgbW9kdWxvIG0gd2FzIHBlcmlvZGljLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgdGhlIGZpcnN0IHRlbiBlbGVtZW50IG9mIHRoZSBGaWJvbmFjY2kgc2VxdWVuY2UsIGFzIHdlbGwgYXMgdGhlaXIgcmVtYWluZGVycyBtb2R1bG8gMTEsIGFyZTo8XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjYwJVwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPm48XC90aD5cclxuXHRcdFx0PHRoPjE8XC90aD5cclxuXHRcdFx0PHRoPjI8XC90aD5cclxuXHRcdFx0PHRoPjM8XC90aD5cclxuXHRcdFx0PHRoPjQ8XC90aD5cclxuXHRcdFx0PHRoPjU8XC90aD5cclxuXHRcdFx0PHRoPjY8XC90aD5cclxuXHRcdFx0PHRoPjc8XC90aD5cclxuXHRcdFx0PHRoPjg8XC90aD5cclxuXHRcdFx0PHRoPjk8XC90aD5cclxuXHRcdFx0PHRoPjEwPFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5GKG4pPFwvdGg+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4yPFwvdGQ+XHJcblx0XHRcdDx0ZD4zPFwvdGQ+XHJcblx0XHRcdDx0ZD41PFwvdGQ+XHJcblx0XHRcdDx0ZD44PFwvdGQ+XHJcblx0XHRcdDx0ZD4xMzxcL3RkPlxyXG5cdFx0XHQ8dGQ+MjE8XC90ZD5cclxuXHRcdFx0PHRkPjM0PFwvdGQ+XHJcblx0XHRcdDx0ZD41NTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5GKG4pIG1vZCAxMTxcL3RoPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTxcL3RkPlxyXG5cdFx0XHQ8dGQ+MjxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzxcL3RkPlxyXG5cdFx0XHQ8dGQ+NTxcL3RkPlxyXG5cdFx0XHQ8dGQ+ODxcL3RkPlxyXG5cdFx0XHQ8dGQ+MjxcL3RkPlxyXG5cdFx0XHQ8dGQ+MTA8XC90ZD5cclxuXHRcdFx0PHRkPjE8XC90ZD5cclxuXHRcdFx0PHRkPjA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPlRoZSBzZXF1ZW5jZSBtYWRlIHVwIG9mIHRoZSByZW1haW5kZXJzIHRoZW4gcmVwZWF0cy4gTGV0IGsobSkgYmUgdGhlIGxlbmd0aCBvZiB0aGUgcmVwZWF0aW5nIHN1YnNlcXVlbmNlOyBpbiB0aGlzIGV4YW1wbGUsIHdlIHNlZSBrKDExKSA9IDEwLjxcL3A+XHJcblxyXG48cD5XYWxsIHByb3ZlZCBzZXZlcmFsIG90aGVyIHByb3BlcnRpZXMsIHNvbWUgb2Ygd2hpY2ggeW91IG1heSBmaW5kIGludGVyZXN0aW5nOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPklmIG0gJmd0OyAyLCBrKG0pIGlzIGV2ZW4uPFwvbGk+XHJcblx0PGxpPkZvciBhbnkgZXZlbiBpbnRlZ2VyJm5ic3A7biAmZ3Q7IDIsIHRoZXJlIGV4aXN0cyBtIHN1Y2ggdGhhdCZuYnNwO2sobSkgPSBuLjxcL2xpPlxyXG5cdDxsaT5rKG0pICZsZTsgbTxzdXA+MjxcL3N1cD4mbmJzcDstIDE8XC9saT5cclxuXHQ8bGk+aygyPHN1cD5uPFwvc3VwPikgPSAzJnRpbWVzOzI8c3VwPihuLTEpPFwvc3VwPjxcL2xpPlxyXG5cdDxsaT5rKDU8c3VwPm48XC9zdXA+KSA9IDQmdGltZXM7NTxzdXA+bjxcL3N1cD48XC9saT5cclxuXHQ8bGk+aygyJnRpbWVzOzU8c3VwPm48XC9zdXA+KSA9IDZuPFwvbGk+XHJcblx0PGxpPklmIG4gJmd0OyAyLCBrKDEwPHN1cD5uPFwvc3VwPikgPSAxNSZ0aW1lczsxMDxzdXA+KG4tMSk8XC9zdXA+PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Rm9yIHRoaXMgcHJvYmxlbSwgeW91IG11c3Qgd3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FsY3VsYXRlcyB0aGUgbGVuZ3RoIG9mIHRoZSByZXBlYXRpbmcgc3Vic2VxdWVuY2UsIGsobSksIGZvciBkaWZmZXJlbnQgbW9kdWxvIHZhbHVlcyBtLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBQLCAoMSAmbGU7IFAgJmxlOyAxMDAwKSwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhIHNldHMgdGhhdCBmb2xsb3cuIEVhY2ggZGF0YSBzZXQgaXMgYSBzaW5nbGUgbGluZSB0aGF0IGNvbnNpc3RzIG9mIHR3byBzcGFjZSBzZXBhcmF0ZWQgaW50ZWdlciB2YWx1ZXMgTiBhbmQgTS4gTiBpcyB0aGUgZGF0YSBzZXQgbnVtYmVyLiBNIGlzIHRoZSBtb2R1bG8gdmFsdWUgKDIgJmxlOyBNICZsZTsgMSwwMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGEgc2V0IHRoZXJlIGlzIG9uZSBsaW5lIG9mIG91dHB1dC4gSXQgY29udGFpbnMgdGhhIGRhdGEgc2V0IG51bWJlciAoTikgZm9sbG93ZWQgYnkgYSBzaW5nbGUgc3BhY2UsIGZvbGxvd2VkIGJ5IHRoZSBsZW5ndGggb2YgdGhlIHJlcGVhdGluZyBzdWJzZXF1ZW5jZSBmb3IgTSwgayhNKS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=