This problem is quite simple. Your task is to calculate the sum of a geometric progression series.

You are given 3 integers R,N and M.

You have to calculate \((R + R^2 + ... + R^N) \bmod M\) .

INPUT :

First line contains an integer T, number of testcases.

\(1 \leq T \leq 10^3\)

Only line of each test case contains R, N and M.

\(1 \leq R,N,M \leq 10^8\)

OUTPUT :

Print answer to each testcase in a new line.