D. Divisibility Game
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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?

Input

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$$$.
Output

For each test case, print one word:

  • Alice if Alice wins;
  • Bob if Bob wins.
Example
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