박테리아 증식 (Large)

미생물을 연구하는 파스칼은 증식 방식이 특이한 박테리아를 발견했다. 어느 순간에 박테리아가 $x$마리 있으면, 이상적인 환경에서는 한 시간 뒤에 $x^x$마리가 된다.

이 성질을 더 깊이 조사하려고, 세 정수 $A$, $B$, $C$가 주어질 때 박테리아 $A$마리가 $B$시간 뒤에 몇 마리가 되는지 구하는 프로그램을 작성한다. 답이 매우 커지므로 그 값을 $C$로 나눈 나머지를 출력한다.

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

각 테스트 케이스는 공백으로 구분된 세 정수로 이루어지고, 순서대로 $A$, $B$, $C$이다.

제한

• $1 \le T \le 500$
• $1 \le A \le 1000$
• $1 \le B \le 1000$
• $1 \le C \le 1000$

각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.

Case #X: N

$X$는 1부터 시작하는 테스트 케이스 번호이고, $N$은 박테리아의 수를 $C$로 나눈 나머지이다.