牛牛

题号：NC238809
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛世界有一款经典的游戏叫做“牛牛”。
经典的“牛牛”游戏规则如下：每位游戏者首先会随机摸取 $5$ 张卡牌（卡牌上的数字为 $1,2,3,\cdots ,10$ ），然后从中选取恰好 $3$ 张卡牌，满足这 $3$ 张卡牌的数字和是 $10$ 的整数倍，接着将剩下的 $2$ 张卡牌的数字求和，结果记为 $S_0$ 。这 $5$ 张卡牌的价值（记为 $v$ ）计算方式如下：

1. 若无论怎么选取都不能选出符合要求的 $3$ 张卡牌，则 $v=0$ ；
2. 若可以选出符合要求的 $3$ 张卡牌，且 $S_0$ 不为 $10$ 的整数倍，则 $v=S_0 \bmod 10$ ；
3. 若可以选出符合要求的 $3$ 张卡牌，且 $S_0$ 为 $10$ 的整数倍，则 $v=10$ 。

可以证明，如果能够选出符合要求的 $3$ 张卡牌，则计算出的价值是唯一的。
牛妹对这款游戏很感兴趣，因此她对这款游戏进行了加强。
加强的“牛牛”游戏规则如下：每位游戏者首先会随机摸取 $n$ 张卡牌（卡牌上的数字为 $1,2,3,\cdots ,m$ ），然后从中选取恰好 $n-2$ 张卡牌，满足这 $n-2$ 张卡牌的数字和是 $m$ 的整数倍，接着将剩下的 $2$ 张卡牌的数字求和，结果记为 $S_0$ 。这 $n$ 张卡牌的价值（记为 $v$ ）计算方式如下：

1. 若无论怎么选取都不能选出符合要求的 $n-2$ 张卡牌，则 $v=0$ ；
2. 若可以选出符合要求的 $n-2$ 张卡牌，且 $S_0$ 不为 $m$ 的整数倍，则 $v=S_0 \bmod m$ ；
3. 若可以选出符合要求的 $n-2$ 张卡牌，且 $S_0$ 为 $m$ 的整数倍，则 $v=m$ 。

同样可以证明，如果能够选出符合要求的 $n-2$ 张卡牌，则计算出的价值是唯一的。
现在牛妹想要测试加强版游戏。她会告诉你 $n$ ， $m$ 以及若干位游戏者的卡牌，她希望你能快速告诉她每一位游戏者卡牌的价值。

输入描述:

输入共  行：
第一行包含一个整数  ，表示游戏者的数量。 
接下来的  行，每  行的数据描述一位游戏者的卡牌情况。 
其中第  行包含  个整数  ，含义见问题描述。 
第  行包含  个整数  ，为这位游戏者的卡牌。
数据满足  ，，，， 。

输出描述:

输出共  行，每行一个整数，表示游戏者卡牌的价值。

示例1

输入

复制

3
5 10
2 10 7 3 1
5 10
2 3 3 3 1
5 10
7 10 9 4 10

输出

复制

3
0
10

说明

对于第一位游戏者，可以先选取  这  张卡牌，剩下  张卡牌为  ，计算得 ，符合价值计算的第  条，故 。 
第一位游戏者也可以先选取  这  张卡牌，剩下  张卡牌为  ，计算得 ，，价值是一样的。 
对于第二位游戏者，可以发现无论如何选取都不能选出和为  的整数倍的  张卡牌，符合价值计算的第  条，因此价值为 。 
注意，虽然  是  的整数倍，但是这不是  张卡牌，因此选择不合法。 
对于第三位游戏者，可以先选取  这  张卡牌，剩下  张卡牌为  ，计算得 ，符合价值计算的第  条，故 。

示例2

输入

复制

10
17 88
45 16 37 77 87 24 64 50 8 3 6 66 75 82 82 22 51
16 24
8 7 2 11 3 8 8 2 2 8 9 21 16 2 10 8
6 40
19 31 33 17 1 30
7 8
6 7 1 8 3 6 6
19 100
8 38 56 67 13 60 76 17 52 77 38 4 74 80 94 50 39 35 35
4 24
13 19 10 15
14 41
41 41 21 29 11 26 1 4 28 23 31 24 7 25
7 12
5 2 8 4 7 5 10
13 80
5 20 57 11 7 58 59 10 30 48 49 62 67
5 33
21 30 23 4 20

输出

复制