小L想请你帮忙计算一下这个式子的结果

(a+b)^pMOD p，其中p是质数。

多组数据

第一行一个T表示数据组数

接下来T行，每行3个正整数a, b, p且保证p是质数 ，输入数据都是long long范围内的正整数。特别的: p <= 2^62

注意p是质数，结合二项式定理可以很容易推得一个结论但是不一定能在时限内通过本题，但稍微再往后推一下就会发现一个非常优美的结论并AC此题

输入数据都是long long范围内的正整数。特别的: p <= 2^62