微生物の研究者であるパスカルは、特殊な増殖の傾向を示すバクテリアを発見した。どうやらそのバクテリアは、ある時点で x 個存在したとすると、理想的な環境下では1時間後に x^x 個に増えるようなのである。</p>

そこであなたは、この興味深い性質をより深く調べるために、入力として 3 つの整数 A, B, C が与えられたときに、A 個のバクテリアが B 時間後には何個になっているかを出力するプログラムを書くことにした。答えの値は非常に大きくなるので、その値を C で割った余りを出力してほしい。

입력 형식

最初の行はテストケースの個数 T を表す正の整数である。それ以降の行に、T 個のケースを表すデータが続く。</p>

それぞれのテストケースは、スペースで区切られた3つの整数からなる1行の文字列で表現される。これらの整数は、順番に A, B, C を表す。

制約

• 1 ≤ T ≤ 500
• 1 ≤ A ≤ 1000
• 1 ≤ C ≤ 1000
• 1 ≤ B ≤ 2

それぞれのテストケースについて、

Case #X: N

という1行の文字列を出力せよ。ここで、X は 1 から始まるテストケースの番号であり、N は求めるべきバクテリアの数を C で割った余りである。

예제 입력

5
1 10 997
2 2 997
2 2 6
461 1 709
461 1000 709

예제 출력

Case #1: 1
Case #2: 256
Case #3: 4
Case #4: 674
Case #5: 461