Cho ba số nguyên dương $N, M, P$, hãy tính $(N^M) mod P$.

Dữ liệu vào

Dòng $1$ là một số nguyên $T$, cho biết số lượng bộ dữ liệu.

$T$ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương $N, M, P$.

Dữ liệu ra

In ra tổng cộng $T$ dòng, mỗi dòng chứa một số nguyên là đáp án.

Ví dụ

Input

3
2 3 7
4 5 6
5 2 9

Output

1
4
7

Ghi chú

Phạm vi dữ liệu

$1 ≤ T ≤ 10^5, 1 ≤ N, M, P ≤ 10^9$