시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 73 24 20 48.780%

문제

피보나치 수열은 아래와 같이 표현된다.

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

각 숫자는 앞의 두 숫자의 합으로 나타내는 것을 알 수 있다.

P와 Q 그리고 n이 주어질 때, P번째 피보나치 숫자를 Q로 나눈 나머지를 구하여라. 

입력

첫번째 라인에는 정수 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 정수 P와 Q가 주어지고,

P(1 ≤ P ≤ 2,000,000,000), Q(1 ≤ Q ≤ 10,000) 이다.

출력

각 테스트 케이스마다 "Case #x: M" 형식으로 출력한다.

x는 테스트 케이스 번호(1부터 시작), M은 P번째 피보나치 숫자를 Q로 나눈 나머지이다.

예제 입력 1

10
5 10
6 25
10 21
32 43
100 100
50 50
25 25
45 67
109 32
128 128

예제 출력 1

Case #1: 5
Case #2: 8
Case #3: 13
Case #4: 15
Case #5: 75
Case #6: 25
Case #7: 0
Case #8: 19
Case #9: 9
Case #10: 69

힌트

W3sicHJvYmxlbV9pZCI6Ijk3MTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWM1ZjRcdWM3NDAmbmJzcDtcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1ZDQ1Y1x1ZDYwNFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+MSwgMSwgMiwgMywgNSwgOCwgMTMsIDIxLCAzNCwgLi4uPFwvcD5cclxuXHJcbjxwPlx1YWMwMSZuYnNwO1x1YzIyYlx1Yzc5MFx1YjI5NCZuYnNwO1x1YzU1ZVx1Yzc1OCBcdWI0NTAgXHVjMjJiXHVjNzkwXHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YzU0YyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5QXHVjNjQwIFEgXHVhZGY4XHViOWFjXHVhY2UwIG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YywgUFx1YmM4OFx1YzlmOCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjJiXHVjNzkwXHViOTdjJm5ic3A7UVx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzVlY1x1Yjc3Yy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YmM4OFx1YzlmOCBcdWI3N2NcdWM3NzhcdWM1ZDBcdWIyOTQgXHVjODE1XHVjMjE4IFRcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YzgxNVx1YzIxOCBQXHVjNjQwIFFcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwLDxcL3A+XHJcblxyXG48cD5QKDEgJmxlOyBQJm5ic3A7JmxlOyAyLDAwMCwwMDAsMDAwKSwgUSgxJm5ic3A7JmxlOyBRJm5ic3A7JmxlOyZuYnNwOzEwLDAwMCkgXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0Jm5ic3A7JnF1b3Q7Q2FzZSAjeDogTSZxdW90OyBcdWQ2MTVcdWMyZGRcdWM3M2NcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD54XHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViYzg4XHVkNjM4KDFcdWJkODBcdWQxMzAgXHVjMmRjXHVjNzkxKSwgTVx1Yzc0MCBQXHViYzg4XHVjOWY4IFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMmJcdWM3OTBcdWI5N2MgUVx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijk3MTEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGaWJvbmFjY2kiLCJkZXNjcmlwdGlvbiI6IjxwPkRlcGljdGVkIGJlbG93IGlzIHRoZSBGaWJvbmFjY2kgc2VxdWVuY2U6PGJyIFwvPlxyXG4xLCAxLCAyLCAzLCA1LCA4LCAxMywgMjEsIDM0LCAuLi48XC9wPlxyXG5cclxuPHA+QXMgeW91IGNhbiBzZWUsIGVhY2ggdmFsdWUgZnJvbSAyIG9ud2FyZHMgaXMgdGhlIHN1bSBvZiB0aGUgcHJldmlvdXMgdHdvIHZhbHVlcy4gR2l2ZW4gUCwgUSBhbmQgbiwgZmluZCB0aGUgbnRoIGZpYm9uYWNjaSBudW1iZXIgbW9kdWx1cyBRLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGdpdmVzIGFuIGludGVnZXIgVCwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiB0d28gaW50ZWdlcnMgUCBhbmQgUS4gUCBpcyBiZXR3ZWVuIDEgYW5kIDIsMDAwLDAwMCwwMDAgaW5jbHVzaXZlLiBRIGlzIGJldHdlZW4gMSBhbmQgMTAsMDAwIGluY2x1c2l2ZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHRoZSBvdXRwdXQgY29udGFpbnMgYSBsaW5lIGluIHRoZSBmb3JtYXQgQ2FzZSAjeDogTSwgd2hlcmUgeCBpcyB0aGUgY2FzZSBudW1iZXIgKHN0YXJ0aW5nIGZyb20gMSkgYW5kIE0gaXMgdGhlIFAmcnNxdW87dGggZmlib25hY2NpIG51bWJlciBtb2R1bHVzIFE8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=