Background

Little A and Little B are both dog lovers and extremely smart. They especially love corgis, so they invented “Corgi Chess”.

Problem Description

Little A and Little B take turns making moves on an $n \times n$ chessboard. Little A moves first, and Little B moves second. Suppose a “corgi” is placed at $(x,y)$. Then the four positions $(x-1,y-1)$, $(x-1,y+1)$, $(x+1,y-1)$, and $(x+1,y+1)$ on the board will all become this corgi’s territory, meaning no other “corgi” can be placed there. If a player cannot place a “corgi” anymore, then that player loses.

Unfortunately, Little C does not really like corgis, so he strongly opposes Little A and Little B playing “Corgi” chess, and he likes to mess up their game. When Little A and Little B have placed a total of $x_i$ “corgis”, Little C will expand the current $w \times w$ board into a $(w+2) \times (w+2)$ board, centered at the center of the current $w \times w$ board. He will interfere a total of $q$ times.

Your task is to determine whether Little A wins or Little B wins. If Little A wins, output A won; otherwise, output B won.

Since they are quite playful, they will play a total of $T$ games.

Note:

1. When Little A and Little B have already played on the original board until no more moves can be made, they will directly jump to Little C’s next interference (if any).

2. Little A and Little B know that Little C will interfere, and they will play according to their optimal strategies.

Due to the data being too large, $x_i$ is given by a random data generator.

Input Format

The first line contains a positive integer $T$, indicating there are $T$ test cases.

Each test case contains one line with three positive integers $n,q,seed$, where the purpose of $seed$ is explained in the hint.

Output Format

Output $T$ lines. Each line should be the string A won or B won.

3
2 5 493
3 8 3219
8 4 1294

B won
A won
B won

Hint

Random Data Generator

In each game, $x_i$ is generated by the following generator:

unsigned long long x[10000005];
unsigned long long xor_shift(unsigned long long &seed){
  return seed^=seed>>12, seed^=seed<<25, seed^=seed>>27, seed*0x2545F4914F6CDD1D;
}
int main(){
  //your code here
  int n,q;
  unsigned long long seed;
  cin>>n>>q>>seed;
  for(int i=1;i<=q;i++){
	x[i]=x[i-1]+((xor_shift(seed)%(unsigned long long)(2*2)+1))*2;
  }
  //your code here
  return 0;
}

Sample Explanation

For the first game, the $x_i$ array is: 6 8 16 18 22.

For the second game, the $x_i$ array is: 8 14 16 24 32 36 38 40.

For the third game, the $x_i$ array is: 4 8 10 16.

Constraints

For $20\%$ of the testdata, $n,q\leq100$.

For $50\%$ of the testdata, $n,q\leq10000$.

For $100\%$ of the testdata, $1 \le T \le 10,2\leq n,q,\sum q \leq 10^7$，$x_i \equiv 0 \pmod 2\ (i\in[1,q]),0 \le seed \le 10^7$。

Translated by ChatGPT 5