피보나치 수의 나머지

피보나치 수열은 다음과 같이 시작한다.

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

첫째 항과 둘째 항은 1이고, 셋째 항부터는 바로 앞 두 항의 합이다. 즉 $F_1 = F_2 = 1$이고, $i \ge 3$이면 $F_i = F_{i-1} + F_{i-2}$이다.

정수 $P$와 $Q$가 주어질 때 $F_P$를 $Q$로 나눈 나머지를 구한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

이어지는 $T$개의 줄에 테스트 케이스마다 정수 $P$와 $Q$가 공백으로 구분되어 주어진다.

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

$x$는 1부터 시작하는 테스트 케이스 번호이고, $M$은 $F_P$를 $Q$로 나눈 나머지이다.

• $1 \le P \le 10000$
• $1 \le Q \le 2000000000$