E. Sherlock and the Mechanical Coin Trap
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

While investigating a peculiar case in Baker Street, Sherlock Holmes discovers a strange mechanical device left by Professor Moriarty. The device consists of N coins placed in a straight line on a table. Each coin shows either Head (H) or Tail (T).

Sherlock notices that the device follows very specific rules:

Sherlock can remove a coin only if it shows Head.

When Sherlock removes the coin at position i, a hidden mechanical switch activates and flips the state of the coins that were originally adjacent to it:

The coin that was originally to its left, if it exists.

The coin that was originally to its right, if it exists.

Two coins are considered neighbors only if they were adjacent in the initial arrangement, regardless of which coins have been removed afterward.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of two lines.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of coins.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$ consisting only of characters 'H' and 'T'.

Output

If it is impossible to remove all coins, print NO.

Otherwise, print YES in the first line.

In the second line, print $$$n$$$ integers — the sequence of removed coin positions in order.

If there are multiple valid answers, print any.

Example
Input
1
2
HH
Output
NO