Bob and Alice are playing a game with the following rules:

- Initially, they have an integer sequence $A_1, A_2, \ldots, A_N$; in addition, Bob has a
*lucky number*$a$ and Alice has a lucky number $b$. - The players alternate turns. In each turn, the current player must remove a non-zero number of elements from the sequence; each removed element should be a multiple of the lucky number of this player.
- If it is impossible to remove any elements, the current player loses the game.

It is clear that one player wins the game after a finite number of turns. Find the winner of the game if Bob plays first and both Bob and Alice play optimally.

### Input

- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains three space-separated integers $N$, $a$ and $b$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

### Output

For each test case, print a single line containing the string `"ALICE"`

if the winner is Alice or `"BOB"`

if the winner is Bob (without quotes).

### Constraints

- $1 \le T \le 10$
- $1 \le N \le 2 \cdot 10^5$
- $1 \le a, b \le 100$
- $1 \le A_i \le 10^9$ for each valid $i$

### Subtasks

Subtask #1 (18 points): $a = b$

Subtask #2 (82 points): original constraints

### Sample 1:

Input

Output

2 5 3 2 1 2 3 4 5 5 2 4 1 2 3 4 5

ALICE BOB

### Explanation:

Example case 1: Bob removes $3$ and the sequence becomes $[1, 2, 4, 5]$. Then, Alice removes $2$ and the sequence becomes $[1, 4, 5]$. Now, Bob is left with no moves, so Alice is the winner.

__Solution__

__Solution__

- If $A$ contains elements which are divisible by both $a$ and $b$, It is optimal for Bob to delete all such elements in the very first move. Turn goes to Alice.
- Now, it is optimal for both players to remove exactly one number they can remove, until one of the players is unable to make a move, thus losing the game. The number of moves Bob can make is Number of elements divisible by $a$ after deleting numbers divisible by both $a$ and $b$. Same way for Alice.

## 0 Comments

If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.