시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 78 26 22 51.163%

문제

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

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+XHJcblxyXG48cD5QXHVjNjQwIFEgXHVhZGY4XHViOWFjXHVhY2UwIG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YywgUFx1YmM4OFx1YzlmOCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjJiXHVjNzkwXHViOTdjJm5ic3A7UVx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzVlY1x1Yjc3Yy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHViNzdjXHVjNzc4XHVjNWQwXHViMjk0IFx1YzgxNVx1YzIxOCBUXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWM4MTVcdWMyMTggUFx1YzY0MCBRXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCw8XC9wPlxyXG5cclxuPHA+UCgxICZsZTsgUCZuYnNwOyZsZTsgMiwwMDAsMDAwLDAwMCksIFEoMSZuYnNwOyZsZTsgUSZuYnNwOyZsZTsmbmJzcDsxMCwwMDApIFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCZuYnNwOyZxdW90O0Nhc2UgI3g6IE0mcXVvdDsgXHVkNjE1XHVjMmRkXHVjNzNjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+eFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmM4OFx1ZDYzOCgxXHViZDgwXHVkMTMwIFx1YzJkY1x1Yzc5MSksIE1cdWM3NDAgUFx1YmM4OFx1YzlmOCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjJiXHVjNzkwXHViOTdjIFFcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5NzExIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmlib25hY2NpIiwiZGVzY3JpcHRpb24iOiI8cD5EZXBpY3RlZCBiZWxvdyBpcyB0aGUgRmlib25hY2NpIHNlcXVlbmNlOjxiciBcLz5cclxuMSwgMSwgMiwgMywgNSwgOCwgMTMsIDIxLCAzNCwgLi4uPFwvcD5cclxuXHJcbjxwPkFzIHlvdSBjYW4gc2VlLCBlYWNoIHZhbHVlIGZyb20gMiBvbndhcmRzIGlzIHRoZSBzdW0gb2YgdGhlIHByZXZpb3VzIHR3byB2YWx1ZXMuIEdpdmVuIFAsIFEgYW5kIG4sIGZpbmQgdGhlIG50aCBmaWJvbmFjY2kgbnVtYmVyIG1vZHVsdXMgUS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBnaXZlcyBhbiBpbnRlZ2VyIFQsIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgdHdvIGludGVnZXJzIFAgYW5kIFEuIFAgaXMgYmV0d2VlbiAxIGFuZCAyLDAwMCwwMDAsMDAwIGluY2x1c2l2ZS4gUSBpcyBiZXR3ZWVuIDEgYW5kIDEwLDAwMCBpbmNsdXNpdmUuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCB0aGUgb3V0cHV0IGNvbnRhaW5zIGEgbGluZSBpbiB0aGUgZm9ybWF0IENhc2UgI3g6IE0sIHdoZXJlIHggaXMgdGhlIGNhc2UgbnVtYmVyIChzdGFydGluZyBmcm9tIDEpIGFuZCBNIGlzIHRoZSBQJnJzcXVvO3RoIGZpYm9uYWNjaSBudW1iZXIgbW9kdWx1cyBRPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d