Ta định nghĩa một hàm ~f(a,n,m)~ như sau:

• ~f(a,n,m) = (a^0 + a^1 + a^2 + ... + a^n)~ mod ~m~

Cho ~t~ truy vấn, mỗi truy vấn nhập vào 3 số nguyên ~a, n, m~, hãy in ra kết quả của hàm ~f(a,n,m)~.

Giới hạn: ~1 \le a \le 10, 1 \le n,m \le 10^9~. Lưu ý, ~m~ là một số nguyên dương bất kì.

Input

• Dòng đầu gồm số nguyên dương ~t~ miêu tả số lượng truy vấn.
• ~t~ dòng sau, mỗi dòng gồm 3 số nguyên dương ~a, n, m~ miêu tả truy vấn đó.

Output

• In ra ~t~ dòng là kết quả của ~t~ truy vấn.

Sample Test

Input:

3
2 3 10000
3 3 123456
2 2 4

Output:

15
40
3