43 人解决，79 人已尝试。
56 份提交通过，共有 357 份提交。
5.4 EMB 奖励。
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$