박테리아의 증식 (Small)

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

정수 $A$, $B$, $C$가 주어질 때 박테리아 $A$마리가 $B$시간 뒤에 몇 마리가 되는지 구하라. 한 시간이 지날 때마다 마리 수 $x$는 $x^x$로 바뀌고, 이 변화가 $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$은 $B$시간 뒤의 박테리아 수를 $C$로 나눈 나머지이다.