题目描述

给你三个正整数 $a,b,c$：

求 $a$ 的 $b$ 次方除以 $c$ 的余数。

输入格式

第一行一个整数 $n$，代表测试数据的组数（不超过$10^5$）。 接下来 $n$ 行，每行 $3$ 个正整数 $a,b,c$。

$0<a,b,c \leq 10^9$

输出格式

对每组输入，输出其运算结果。

4
2 5 7
3 7 9
12 5 97
139493779 741299297 162330477

4
0
27
52410622