Once the famous Sir NKP went to give a speech in Oxford University . During the Question hour , one Student in the hall raised a question to find
The sum of powers of first N natural numbers modulus some Natural Number P.
It was a geeky ONE ! but Sir NKP smiled and wrote the algorithm to compute the above asked problem ! Unfortunately the paper in which he wrote the solution went missing due to that irresponsible student !
Can you Devise a code for the student ?
CONSTRAINTS:
1 ≤ T ≤ 10
1 ≤ N ≤
1 ≤ K ≤
1 ≤ P ≤
INPUT:
First line of input contains T , the number of test cases . Each test case contains three space separated integers N,K,P.
OUTPUT:
For each test case output the value (++...+) mod P in a single line.