给定三个正整数 ，请计算以下表达式的值： 即先求 的值 ，再以该结果为指数计算 的值，最后对模数 取模。

输入描述:

第一行输入一个整数 表示测试用例数量。接下来 行，每行输入三个整数 。

输出描述:

对于每个测试用例，输出一行一个整数，表示 的值。