Multiples Color Flipping Game

There is an array of length \(n\) whose cells are colored either white or black. Two players (A and B) play a game alternately according to the following rules:

• On each turn, the current player must choose a cell with index \(x\) (1-indexed) that is white.
• Then, the player chooses an integer \(k\) such that \(1 \le k \le \lfloor n/x \rfloor\). For the chosen \(x\) and \(k\), the colors of the cells at indices \(x, 2x, \dots, kx\) are flipped (white becomes black and vice versa).
• The player who is unable to make a move loses.

Player A (the first mover) is interested in several queries. In each query an initial state of the array is given. Determine whether player A has a winning strategy if both players play optimally.

Note on optimal play:

Observe that a "safe move" always exists: if there is a white cell at index \(x\), one may choose \(k=1\) so that only cell \(x\) is flipped (from white to black) leaving the other cells unchanged. However, when the total number of white cells is even, a safe move might hand the advantage to the opponent. In that case a move that flips more than one cell might be used to change the parity of the total white count. In fact, if we denote for a move on cell \(x\) with parameter \(k\) the set of affected indices as \(S = \{x,2x,\dots,kx\}\) and let \(w = |\{ i \in S : \text{cell } i \text{ is white} \}|\), then the net change in white count is
\(\Delta = (k - w) - w = k - 2w\).
Thus a player can choose a move (whenever possible) that changes the parity of the white count favorably.

A key observation is that a safe move (choosing \(k=1\)) always removes exactly one white cell. Hence, if only safe moves are available, the outcome would be decided by the parity of the white count. However, if there is any white cell whose index \(x\) satisfies \(x \le n/2\) (i.e. \(\lfloor n/x \rfloor \ge 2\)), then a move with \(k\ge2\) is available that can flip an even number of cells (since \(k\) even gives \(\Delta\) even) and potentially preserve a winning parity even when the total number of white cells is even.

Thus, the winning condition can be summarized as follows:

1. If there are no white cells initially, player A loses.
2. If the total number of white cells is odd, player A wins (by, for instance, using the safe move \(k=1\)).
3. If the total number of white cells is even, then player A wins if and only if there exists at least one white cell at an index \(x\) with \(x \le \lfloor n/2 \rfloor\) (so that a \(k \ge 2\) move is available to adjust the parity). Otherwise, if all white cells are at indices greater than \(n/2\), only safe moves are possible, and the parity advantage means player A loses.

inputFormat

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

For each test case:

• The first line contains an integer \(n\) (the length of the array).
• The second line contains a string of length \(n\) consisting only of characters 'W' and 'B', representing a white or black cell respectively.

outputFormat

For each test case, output a single line containing Yes if player A has a winning strategy, or No otherwise.

sample

1
2
WW

Yes