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$

35 人解决,65 人已尝试。

43 份提交通过,共有 291 份提交。

5.6 EMB 奖励。

创建: 2 年,10 月前.

修改: 2 年,9 月前.

最后提交: 5 月前.

来源: HackerRank