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

输入描述:

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

输出描述:

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

备注:

本题已于下方时间节点更新，请注意题解时效性：1. 2025-11-28 优化题面文本与格式；缩小 的范围（从 缩小到 ）。模板题为便于测试，将时间限制扩充至 5s，空间限制扩充至 1024MB。