Statement : D. Divisibility Game

Alice and Bob are playing a game. They have an array $a$ of $n$ elements and an array $b$ of $m$ elements.

The players take turns. Alice goes first. On their turn, each player chooses a number $x$ from array $a$ and a number $y$ from array $b$. Alice has her own rule for choosing $x$ and $y$, and Bob has his:

• Alice must choose $x$ and $y$ such that $y$ is divisible by $x$.
• Bob must choose $x$ and $y$ such that $y$ is not divisible by $x$.

After choosing $x$ and $y$, $y$ is removed from the array $b$ (but $x$ remains in $a$). When $y$ is removed from $b$, if there are multiple occurrences of $y$, only one is removed. The player who cannot make a move loses.

Who will win if both players play optimally?

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

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

The second line of each test case contains $n$ integers $a_{i}$ ($1 \le a_{i} \le n + m$) — the elements of the array $a$.

The last line of each test case contains $m$ integers $b_{i}$ ($1 \le b_{i} \le n + m$) — the elements of the array $b$.

Additional constraints on the input:

• the sum of $n$ over all test cases does not exceed $10^6$;
• the sum of $m$ over all test cases does not exceed $10^6$.

For each test case, print one word:

• Alice if Alice wins;
• Bob if Bob wins.

Input

3
9 3
3 2 4 2 2 4 4 2 4
6 7 12
10 3
3 2 5 4 2 5 3 4 4 4
10 7 13
1 5
1
1 2 3 4 5

Output

Alice
Bob
Alice

Note

Consider the first test case. Let’s show how Alice wins through the moves:

• Alice’s move: $x = 3, y = 6$ (after this, $6$ will be removed from $b$, resulting in $b = [7, 12]$)
• Bob’s move: $x = 3, y = 7$ (Bob will choose $y = 7$ on his turn anyway, since there is no $x$ that does not divide $y = 12$, after this move $b = [12]$)
• Alice’s move: $x = 4, y = 12$ (after this move, $b$ becomes empty)
• Bob’s move: Bob loses, as he cannot make a move