Alice and Bob are playing a game with $n$ grains of sand.

The two players take turns removing sand, with Alice going first. In each turn, the number of grains a player removes must not exceed $k$, and it must be a common divisor of all the amounts of sand previously removed (including the opponent's). Specifically, when Alice removes sand for the first time, the amount is not subject to the second constraint; she only needs to ensure it does not exceed $k$.

The player who removes the last grain of sand wins. Alice wants to know if she can win, assuming both players play optimally.

Input

The first line contains an integer $T$ ($1 \le T \le 10^4$), representing the number of test cases.

Each of the next $T$ lines contains two integers $n$ and $k$ ($1 \le n, k \le 10^9$), as described in the problem statement.

Output

Output $T$ lines in total. For each test case, if Alice has a winning strategy, output Alice; otherwise, output Bob.

Examples

Input 1

3
3 2
4 3
5 1

Output 1

Alice
Bob
Alice