1059:身份证号

某个国王给自己的臣民编号，按照臣民申请的顺序从1号开始编起，最大编到m号。如果人数太多号码不够用，则当编到m号以后，下一个臣民重复地从1号开始编起，如此循环地使用1~m之间的数字作为编号。这个王国里有a的b次方个臣民，请问最后一个臣民的编号是多少。

1个正整数n，表示测试案例的数量。
每组测试案例中，有三个正整数m、a、b，其中m表示最大可用的编号数字，a的b次方表示臣民的数量。（m<100000000, a<10000, b<10000）

针对每组案例，输出一个数字，表示最后一个臣民的编号。
每组案例输出后都要换行。

1
10 3 4

1

3的4次方是81，可用的编号从1到10循环使用，第81个臣民的编号应该是1