题目描述

给出 $T$ 组数据，每组给出 $x$，$y$，$N$。请求出 $x^y \mod N$ 的值。

输入格式

输入第一行一个整数 $T$，表示数据组数，$T\le 10^5$。

接下来 $T$ 行，每行三个整数 $x, y, N$，$x,N\le 10^5$，$y\le 10^9$。

输出格式

对于每一组数据，输出单行一个整数，表示 $x^y \mod N$ 的结果。

2
2 3 5
2 2147483647 13

3
11