3332. 无限剑制的终焉

单点时限: 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$,表示测试数据组数。$(1 \leq T \leq 10001)$

对于每组测试数据:
每行两个整数,$n$ 和 $k$。$(1 \leq n \leq 10^{16}, 1 \leq k \leq 10^9)$

输出格式

输出余数。

样例

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

提示

$111 \bmod 3 = 0 $
$1111 \bmod 7 = 5 $
$11111 \bmod 18 = 5$

37 人解决,71 人已尝试。

47 份提交通过,共有 318 份提交。

5.6 EMB 奖励。

创建: 4 年前.

修改: 3 年,12 月前.

最后提交: 6 月,2 周前.

来源: HackerRank