Sum Game#13008

Sum Game

2 seconds
512 megabytes
Hard

Ana and Bob play the following game.

First, Bob chooses a sequence of positive integers a_1, a_2, \dots, a_n. Then Ana is allowed to perform the following operations.

After that, Ana computes the sum of the remaining numbers. She wins the game if she can obtain a sum that is divisible by . Otherwise, Bob wins.

Given and , determine which player has a winning strategy.

Input

The first line contains a single integer – the number of test cases.

Each of the next lines contains two integers and .

1 \le t \le 10^5,

1 \le n, m \le 10^{18}.

Output

For each test case, output a single line.

  • Ana – if Ana has a winning strategy,

  • Bob – if Bob has a winning strategy.

Examples

Example

Loading
Loading

Note

In the first test case, Bob can choose a_1 = 3.

In the second test case, no matter how Bob chooses a_1, a_2, Ana has a winning strategy.