Alice and Bob always like playing games with each other and today they found a new game about primes.

There are two positive integers $x$ and $y$ in the game, and Alice and Bob move in turn. At each turn, the current player can choose one integer and subtract it by $1$ (making $(x, y)$ to $(x - 1, y)$ or to $(x, y - 1)$). The game ends when one of following conditions is met and the winner is specified at the same time:

• When $x$ or $y$ equals to $K$: Bob wins.
• When $x$ and $y$ are both primes: Alice wins.
• When both of the previous conditions are satisfied at the same time: Bob wins.

Now $x, y, K$ and who moves first are given, can you determine who will finally win the game if they both play optimally?

Input

The first line of input contains an integer $T$, representing the number of test cases. Then following $T$ lines and each line contains one test case.

For each test case, there are four integers $x, y, K$ and $w$ separated by exactly one space. $x,y,K$ are mentioned above. $w = 0$ when Alice moves first and $w = 1$ when Bob moves first.

Output

For each test case, you should output Case x: name in one line, where x indicates the case number starting from 1, and name is the player who will win the game.

Examples

Input 1

4
4 9 2 0
7 10 2 0
6 39 2 0
5 28 2 0

Output 1

Case 1: Alice
Case 2: Alice
Case 3: Alice
Case 4: Bob

Note

$1 \le T \le 100$

$2 \le x, y \le 10^6$

$2 \le K \le \min(x, y)$

$0 \le w \le 1$

For $90\%$ test cases: $\max(x, y) \le 1000$.