Pendu wanted to play cricket. But, as he is fat, he can't run. He asked his friend Mahi to be his runner. Mahi agreed to help him if he can find the answer to his question.

He gave Pendu three integers $N,\space a, \space b$ and asked him to calculate $f(N,a)$ modulo $(a^b)$, where 

                            $f(X,y) = \Large{\frac{X!}{y^{(\textbf{max}\space \textbf{power}\space of \space \textbf{y} \space in \space \textbf{X!})}}}$

As Pendu is also very weak in maths, he needs assistance. Help him to find the answer so that he can play cricket.

INPUT FORMAT

The first line of the input contains a single integer T denoting the number of test cases.
Each test case contains three space-separated integers $N, \space a, \space b$

OUTPUT FORMAT

Output a single integer denoting the required answer.

INPUT CONSTRAINTS

$1\le T \le 100 \\ 0\le N \le10^{18} \\ a \space\text{is a} \space\textbf{prime number}\\ 1 \le a^b \le 10^5$