CF2145F.Long Journey

There is a strip divided into cells, numbered from $0$ to $m$ from left to right. You are controlling a chip that is initially in the cell $0$.

There is a trap in each cell; they are activated according to the following rules:

• at the end of moves $1, (1+n), (1+2n), \dots$, traps are activated in cells $x$ where $x \bmod a_1 = b_1$;
• at the end of moves $2, (2+n), (2+2n), \dots$, traps are activated in cells $x$ where $x \bmod a_2 = b_2$;
• $\cdots$
• at the end of moves $n, (n+n), (n+2n), \dots$, traps are activated in cells $x$ where $x \bmod a_n= b_n$.

In one turn, you can either move from the current cell to the next or stay in place. Then all the traps for this turn are activated. If the chip is in a cell with an activated trap at the beginning of the turn, the game ends.

Your task is to calculate the minimum number of turns to reach the cell $m$, or report that it is impossible. If the chip reaches the cell $m$ and at the end of the same turn, a trap in the cell $m$ activates, it is not considered a valid way to reach the cell $m$.

有一条被划分为若干格子的长条，格子从左到右编号为 $0$ 到 $m$。你控制一个初始位于格子 $0$ 的芯片。

每个格子中均设有一个陷阱，其激活规则如下：

• 在第 $1,\ (1+n),\ (1+2n),\ \dots$ 步结束时，所有满足 $x \bmod a_1 = b_1$ 的格子 $x$ 中的陷阱被激活；
• 在第 $2,\ (2+n),\ (2+2n),\ \dots$ 步结束时，所有满足 $x \bmod a_2 = b_2$ 的格子 $x$ 中的陷阱被激活；
• $\cdots$
• 在第 $n,\ (n+n),\ (n+2n),\ \dots$ 步结束时，所有满足 $x \bmod a_n = b_n$ 的格子 $x$ 中的陷阱被激活。

每一轮中，你可以选择将芯片从当前格子移动至右侧相邻格子，或保持不动。随后，该轮对应的所有陷阱将被激活。若芯片在本轮开始时所处格子中存在已被激活的陷阱，则游戏立即结束。

你的任务是计算到达格子 $m$ 所需的最少轮数；若无法到达，则报告不可能。特别地，若芯片在某轮中抵达格子 $m$，但该轮结束时格子 $m$ 的陷阱恰好被激活，则此路径不被视为有效到达格子 $m$ 的方式。

The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 10$; $1 \le m \le 10^{12}$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($2 \le a_i \le 10$).

The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($0 \le b_i \lt a_i$).

第一行包含一个整数 $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$）。

For each test case, print a single integer — the minimum number of turns to reach cell $m$. If it is impossible, print -1.

对于每个测试用例，输出一个整数——到达单元格 $m$ 所需的最少步数。如果无法到达，则输出 $-1$。