Joker is back again with his destructive plan . He has set N bombs in various parts of Gotham city and has challenged the police department to defuse all bombs in one day . City can be treated as a 1-D line with 'N' bombs situated in such a manner that distance of 1^st bomb is 'x' , 2nd bomb is ' x² ' , 3rd bomb is ' x³ ' ....... nth bomb is ' xⁿ ' , where ' x ' is measured from the start (left end ) . Since the number of bombs planted is very large , Gordon and his team find it impossible to diffuse all the bombs in one day and once again Gordon asks for Batman's help . He keeps his bomb diffusing squad ready at the start and requests batman to bring all the bombs back to the start . Since the bombs are very heavy , batman can carry only one bomb at a time . For each bomb , he first travels upto the bomb location and then carry it back upto the start and thus covering the same distance ( bomb's distance from the start ) twice . For example for N=4 , total distance covered by batman is
x + x + x² + x² + x³ + x³ + x⁴ + x⁴ where x is the distance of the first bomb in kms. Now Batman is wondering how much distance he has to cover in order to bring all bombs back to the start but he is little weak in calculations involving large numbers and asks for your help to calculate the total distance he has to cover . Since the total distance can be very large , he wants you to calculate the total distance mod M , i.e he wants total_distance % M.

Input

First line of input contains integer t , number of test cases. Each t lines contains contains 3 integers N - number of bombs planted in the city , x - distance of first bomb and M - modulo .

Output

Each line of output contains a single integer , the required answer.

Constraints

1<=T<=50
1<=N,x<=10⁹
1< M<=100000 (10⁵)