有一个条带分为多个单元,从左到右编号为 $$$0$$$ 到 $$$m$$$。您正在控制最初位于单元$$$0$$$中的芯片。
每个牢房内都有一个陷阱;它们根据以下规则激活:
- 在移动 $$$1、(1+n)、(1+2n)、\dots$$$ 结束时,在单元格 $$$x$$$ 中激活陷阱,其中 $$$x \bmod a_1 = b_1$$$;
- 在移动 $$$2、(2+n)、(2+2n)、\dots$$$ 结束时,陷阱在单元格 $$$x$$$ 中被激活,其中 $$$x \bmod a_2 = b_2$$$;
- $$$\cdots$$$
- 在移动 $$$n、(n+n)、(n+2n)、\dots$$$ 结束时,陷阱在单元格 $$$x$$$ 中激活,其中 $$$x \bmod a_n= b_n$$$。
在一个回合中,你可以从当前单元格移动到下一个单元格,也可以留在原地。然后本回合的所有陷阱都会被激活。如果筹码在回合开始时位于已激活陷阱的单元格中,则游戏结束。
你的任务是计算到达单元格$$$m$$$的最小转弯数,或者报告这是不可能的。 如果筹码到达单元格 $$$m$$$ 并且在同一回合结束时,单元格 $$$m$$$ 中的陷阱激活,则不被视为到达单元格 $$$m$$$ 的有效方式.
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10$$$; $$$1 \le m \le 10^{12}$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$2 \le a_i \le 10$$$)。
第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$0 \le b_i \lt a_i$$$)。
输出
对于每个测试用例,打印一个整数 - 到达单元格 $$$m$$$ 的最小圈数。如果不可能,则打印 -1.
示例
输入复制
52 52 20 12 52 21 01 7324 2123981517133 2 5 20 1 3 02 43 40 0
输出复制
56-14247963034245