C. Feeding Beavers
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

It's dinner time, and Busy Beaver has to feed his baby beavers.

Busy Beaver has $$$N$$$ baby beavers, numbered from $$$1$$$ to $$$N$$$. The older baby beavers have bigger indices than the younger ones; for example, beaver $$$1$$$ is the youngest while beaver $$$N$$$ is the oldest.

Busy Beaver also has $$$2N$$$ dishes, which are numbered from $$$1$$$ to $$$2N$$$. If a beaver eats dish $$$i$$$, its satisfaction will increase by $$$i$$$. Each beaver starts with $$$0$$$ satisfaction.

Now, Busy Beaver wants to distribute the dishes amongst his baby beavers subject to the following constraints:

  • Each beaver should get exactly two dishes.
  • After all dishes are consumed, older beavers should have at least as much satisfaction as younger beavers. Formally, for any $$$i, j$$$ with $$$1 \leq i \lt j \leq N$$$, beaver $$$i$$$'s satisfaction should not exceed beaver $$$j$$$'s satisfaction.
  • The parity of beaver $$$i$$$'s satisfaction should be $$$c_i$$$ (odd or even).

Determine if there exists a way to feed all $$$N$$$ beavers that respects these constraints. Additionally, if the task is possible, print any valid assignment of dishes to beavers.

Input

Each test contains multiple test cases. The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 10^4$$$) — the number of test cases. The description of each test case follows.

The first line of each test case contains an integer $$$N$$$ ($$$1 \le N \le 10^5$$$) — the number of baby beavers.

The second line of each test case contains a string $$$c$$$ of length $$$N$$$, where each of the characters $$$c_i$$$ is either 'O' or 'E'. If $$$c_i$$$ is 'O', the beaver $$$i$$$ wants its satisfaction to be an odd number. If $$$c_i$$$ is 'E', the beaver $$$i$$$ wants its satisfaction to be an even number.

It is guaranteed that the sum of $$$N$$$ across all test cases is no more than $$$10^5$$$.

Output

For each test case, if it is possible to feed the beavers, output "YES" (without quotes) on the first line. Next, print $$$N$$$ lines describing how to feed each beaver. The $$$i$$$-th of these lines should contain two integers, which denote the indices of the two dishes that will be given to beaver $$$i$$$.

If it is impossible to feed the beavers, output "NO" (without quotes).

You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).

Scoring

There are two subtasks for this problem.

  • ($$$25$$$ points): For each test case, the string $$$c$$$ either only consists of 'O's or only consists of 'E's.
  • ($$$75$$$ points): No additional constraints.
Example
Input
3
4
OEEO
7
OEOEOEO
6
OOOOOO
Output
YES
2 3
5 1
4 8
7 6
NO
YES
1 12
2 11
3 10
4 9
5 8
6 7
Note

In the first test case, one possible way to feed the beavers is as follows:

  • Feed dishes $$$2$$$ and $$$3$$$ to beaver $$$1$$$. Beaver $$$1$$$ gains satisfaction of $$$5$$$, which is odd.
  • Feed dishes $$$5$$$ and $$$1$$$ to beaver $$$2$$$. Beaver $$$2$$$ gains satisfaction of $$$6$$$, which is even.
  • Feed dishes $$$4$$$ and $$$8$$$ to beaver $$$3$$$. Beaver $$$3$$$ gains satisfaction of $$$12$$$, which is even.
  • Feed dishes $$$7$$$ and $$$6$$$ to beaver $$$4$$$. Beaver $$$4$$$ gains satisfaction of $$$13$$$, which is odd.

The satisfaction of the four beavers in increasing order of age are $$$[5, 6, 12, 13]$$$. It can be checked that this assignment satisfies the conditions.

In the second test case, it can be shown that the task is impossible.