给你一个数组 $$$a[0 \ldots n - 1] = [a_0, a_1, \ldots, a_{n - 1}]$$$ 仅由 0 和 1 组成。请注意,在这个问题中,与其他问题不同,数组索引是从零开始编号的,而不是从一开始。
在一个步骤中,数组 $$$a$$$ 根据以下规则被长度为 $$$n$$$ 的另一个数组替换:
1. 首先,定义一个新数组 $$$a^{\rightarrow d}$$$ 为数组 $$$a$$$ 向右循环移位 $$$d$$$ 个单元格。该数组的元素可以定义为 $$$a^{\rightarrow d}_i = a_{(i + n - d) \bmod n}$$$,其中 $$$(i + n - d) \bmod n$$$ 是 $$$i + n - d$$$ 除以 $$$n$$$ 的整数除法的余数。 这意味着整个数组 $$$a^{\rightarrow d}$$$ 可以表示为一个序列 $$$$$$a^{\rightarrow d} = [a_{n - d}, a_{n - d + 1}, \ldots, a_{n - 1}, a_0, a_1, \ldots, a_{n - d - 1}]$$$$$$
2. 然后将数组 $$$a_i$$$ 的每个元素替换为 $$$a_i \,\&\, a^{\rightarrow d}_i$$$,其中 $$$\&$$$ 是逻辑“AND”运算符。
例如,如果 $$$a = [0, 0, 1, 1]$$$ 且 $$$d = 1$$$,则 $$$a^{\rightarrow d} = [1, 0, 0, 1]$$$,第一步后 $$$a$$$ 的值为 $$$[0 \,\&\, 1, 0 \,\&\, 0, 1 \,\&\, 0, 1 \,\&\, 1]$$$,即 $$$[0, 0, 0, 1]$$$。
当数组停止变化时,该过程结束。对于给定的数组 $$$a$$$,在过程结束时确定它是否仅由零组成。如果是,还请找出该过程在完成之前将执行的步骤数。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。
接下来的 $$$2t$$$ 行包含测试用例的描述。
每个测试用例描述的第一行包含两个整数:$$$n$$$ ($$$1 \le n \le 10^6$$$) — 数组大小和 $$$d$$$ ($$$1 \le d \le n$$$) — 循环移位偏移量。描述的第二行包含 $$$n$$$ 以空格分隔的整数 $$$a_i$$$ ($$$0 \le a_i \le 1$$$) — 数组的元素。
保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。
输出
打印 $$$t$$$ 行,每行包含相应测试用例的答案。测试用例的答案应该是一个整数——数组第一次只包含零之前的步骤数。如果进程结束后数组中仍有等于$$$1$$$的元素,则打印-1。
示例
输入 #1
5 2 1 0 1 3 2 0 1 0 5 2 1 1 0 1 0 4 2 0 1 0 1 1 1 0
输出 #1
1 1 3 -1 0
注意
在第三个示例测试用例中,数组将更改如下:
1. 开头 $$$a = [1, 1, 0, 1, 0]$$$,$$$a^{\rightarrow 2} = [1, 0, 1, 1, 0]$$$。它们的逐个元素“AND”等于 $$$$$$[1 \,\&\, 1, 1 \,\&\, 0, 0 \,\&\, 1, 1 \,\&\, 1, 0 \,\&\, 0] = [1, 0, 0, 1, 0]$$$$$$
2. 现在 $$$a = [1, 0, 0, 1, 0]$$$,然后 $$$a^{\rightarrow 2} = [1, 0, 1, 0, 0]$$$。它们的逐个元素“AND”等于 $$$$$$[1 \,\&\, 1, 0 \,\&\, 0, 0 \,\&\, 1, 1 \,\&\, 0, 0 \,\&\, 0] = [1, 0, 0, 0, 0]$$$$$$
3. 最后,当 $$$a = [1, 0, 0, 0, 0]$$$ 时,我们得到 $$$a^{\rightarrow 2} = [0, 0, 1, 0, 0]$$$。它们的逐个元素“AND”等于 $$$$$$[1 \,\&\, 0, 0 \,\&\, 0, 0 \,\&\, 1, 0 \,\&\, 0, 0 \,\&\, 0] = [0, 0, 0, 0, 0]$$$$$$
在第四个示例测试用例中,数组向右移动 $$$2$$$ 时不会改变,因此每个元素将被计算为 $$$0 \,\&\, 0$$$ 或 $$$1 \,\&\, 1$$$,因此不会改变其值。所以答案是 -1,数组永远不会只包含零。