题目描述

今天下了一场大雪。

你像往常一样，从温暖的被窝中艰难地爬出，背起一个沉重的笔记本电脑，走上了去内卷的路上。

这是愉悦的周末，同样令人愉悦的是，幸运的你被n位天神选中，只要依次你回答出他们的问题，你就可以前往没有内卷的二次元世界。

而愚蠢的天神们只能想出一个问题，那就是，天神给出三个数a，b，c，请你说出：a^b mod c的值。

天上一天，你的寿命消逝十年。为了能更多地享受二次元生活，请身为程序员的你，运用身边的电脑设计程序，以最快的速度回答天神问的问题（要不然，你就G了哦）。

输入格式

第一行输入n，1≤n≤1e6

接下来n行，输入a，b，c，1≤a,b,c≤2e9

输出格式

输出n行，即a^b mod c的值

样例

2 
3 2 5 
4 3 9

4 
1

提示

by 陈代睿