Migrated from Lutece 1477 Magic boy Bi Luo with his excited gcd problem

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

As we know, Bi Luo is a magic boy, he always has some excited questions , now a new question comes.

You are given a unknow sequence $A$, each of its element is belong to $[1,M]$, you may easy to caculate there are $M^{|A|}$ different sequences.

But Bi Luo is also a powerful wizard, but these years, he just do a little bit of work,he now wants to break this bad situation. he find the key to break the situation is to find the number of different excited sequences among all of the possible sequences of $A$. But Bi Luo now is busy in fighting at Highway 66. so this important mission is given to you. can you solve it ?

• A sequence $a$ is excited if and only if for all of its different index( $i,j$ ) satisfy $GCD( a_i , a_j ) = 1$

Input

First Line is an positive integer $T$ , ( $1 \leq T \leq 40$ ) , represents there are $T$ test cases.

For each test case:

The first line contains two positive integers $N , M$.( $1 \leq N\leq 10^{15}$ , $1 \leq M \leq 250$ )

Output

For tht $i$-$th$ test case , first output Case #i: , then output one integer represents the number excited sequence,because the number may be large , so you need to output the number mod $841815229$.

Samples

1
5 3

Case #1: 31

Resources

“玲珑杯”ACM比赛 Round #2