给定一个整数数组 $$$a_1, a_2, \ldots, a_n$$$ 和一个数字 $$$k$$$ ($$$2 \leq k \leq 5$$$)。在一项操作中,您可以执行以下操作:
- 选择一个索引 $$$1 \leq i \leq n$$$,
- 设置$$$a_i = a_i + 1$$$。
求使数组 $$$a_1 \cdot a_2 \cdot \ldots \cdot a_n$$$ 中所有数字的乘积能被 $$$k$$$ 整除所需的最少运算次数。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。然后是测试用例的描述。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \leq n \leq 10^5$$$, $$$2 \leq k \leq 5$$$) — 数组 $$$a$$$ 的大小和数字 $$$k$$$。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出使数组中所有数字的乘积可被 $$$k$$$ 整除所需的最少操作数。
示例
输入 #1
15 2 5 7 3 3 3 7 4 1 5 2 9 7 7 3 9 5 5 5 4 1 2 3 7 4 9 5 1 5 9 5 1 3 4 6 3 6 3 4 6 1 5 3 4 1 5 9 4 4 1 4 1 1 3 4 3 5 3 4 5 8 9 9 3 2 5 1 6 2 5 10 10 4 5 1 6 1 1 2 5 7 7
输出 #1
2 2 1 0 2 0 1 2 0 1 1 4 0 4 3
注意
在第一个测试用例中,我们需要选择索引 $$$i = 2$$$ 两次。之后,数组将是 $$$a = [7, 5]$$$。数组中所有数字的乘积为 $$$35$$$。
在第四个测试用例中,数组中数字的乘积是$$$120$$$,它已经可以被$$$5$$$整除,因此不需要任何操作。
在第八个测试用例中,我们可以通过以任意顺序选择 $$$i = 2$$$ 和 $$$i = 3$$$ 来执行两个操作。之后,数组将是 $$$a = [1, 6, 10]$$$。数组中数字的乘积是 $$$60$$$。