1059:身份证号

时间限制: 2 S | 内存限制: 65536 KB
Accept: 0 | Submit: 0
[提交] [状态] [讨论版]
描述

某个国王给自己的臣民编号,按照臣民申请的顺序从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

HINT

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

来源
第五届编程大赛