对于给定的三个正整数 ，计算 。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：一行上输入三个整数 代表底数、指数和模数。

输出描述:

对于每一组测试数据，在一行上输出一个整数，代表式子的答案。