2017.8.22 ACM 训练赛

C. 无限剑制的终焉

单点时限: 3.0 sec

内存限制: 256 MB

I am the bone of my sword.
Steel is my body, and fire is my blood.
I have created over a thousand blades.
Unknown to Death.
Nor known to Life.
Have withstood pain to create many weapons.
Yet, those hands will never hold anything.
So as I pray, unlimited blade works.

在固有结界“无限剑制”中,卫宫开始思考这样一个问题,如果把每一把剑看做数字 1,那么 n 把剑连在一起模 k 的余数是多少呢?

输入格式

第一行一个整数 T,表示测试数据组数。(1T10001)

对于每组测试数据:
每行两个整数,nk(1n1016,1k109)

输出格式

输出余数。

样例

Input
3
3 3
4 7
5 18
Output
0
5
5

提示

111mod3=0
1111mod7=5
11111mod18=5