Cho ~3~ số nguyên ~N~, ~A~, ~P~, xây dựng danh sách ~N~ phần tử như sau :

• ~a_{0} = (A * A)~ % ~P~

• ~a_{i} = (a_{i-1} * A)~ % ~P~ với ~0 < i < N~.

Hãy đếm số lượng các cặp số ~0 ≤ i < j < N~ sao cho ~a_{i} > a_{j}~.

Input

• Dòng đầu tiên là số test cases ~T~ ~(1 ≤ T ≤ 10)~

• Mỗi dòng tiếp theo mô tả ~1~ testcase, gồm ~3~ số nguyên ~N~, ~A~, và ~P~ là số nguyên tố.

Output

• In ra số lượng cặp số theo yêu cầu.

Constraints

• ~1 ≤ N ≤ 10^{7}~
• ~1 ≤ A ≤ 10^{9}~
• ~P > 10^{9}~

Sample Input:

2
70 1356 1000000297
63 159 1000002937

Sample Output:

1230
856