J. Bridge III
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Bidding is the first phase of a bridge game where players communicate their hand strength and distribution to determine the contract (the final goal for the round). The rules of bidding are listed as follows.

  • Bid Structure:
    • An auction consists of a number (from $$$1$$$ to $$$7$$$) and a suit.
    • Suit hierarchy (lowest to highest): Club (C), Diamond (D), Heart (H), Spade (S), No Trump (N).
    • To outrank another auction:
      • Higher number, OR
      • Same number but higher-ranked suit.
      • Example: 2C $$$ \gt $$$ 1S (higher number), 2N $$$ \gt $$$ 2C (higher suit).

  • Players and Turns:
    • Players take turns in order: $$$1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 1\dots$$$
    • Partnerships: Player $$$1$$$ & $$$3$$$ are partners; Player $$$2$$$ & $$$4$$$ are partners.
    • Opponents are non-partner players.

  • Allowed Actions:
    • Auction: Bid higher than the last valid auction.
      • If there is no previous valid auction, the player can bid any auction.
    • Pass (P): Skip without bidding.
    • Double (X):
      • Only allowed if the last non-pass bid was an auction by an opponent.
    • Redouble (XX):
      • Only allowed if the last non-pass bid was a double by an opponent.

  • Ending Conditions:
    • All four players pass initially, OR
    • Three consecutive passes occur after any non-pass bid.

You're given a bidding sequence. Determine if it is both valid (follows all rules) and complete (meets an ending condition).

Input

Each test contains multiple tests. The first line contains one integer $$$t$$$ ($$$1\le t\le 100$$$) — the number of test cases. The description of each test case follows.

The first line of each test case contains one integer $$$n$$$ ($$$1\le n\le 320$$$) — the length of the bidding sequence.

The second line contains $$$n$$$ strings which indicate each player's bids. It is guaranteed that the bids are valid.

Output

For each test case, if the bidding sequence is valid, output "YES"; otherwise, output "NO". You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Example
Input
6
4
P P P P
5
P P P P X
5
P 1C P P P
6
P P 1C 1D P P
8
P 1H X XX X P P P
12
1S P 2C P 2D P 4S X XX P P P
Output
YES
NO
YES
NO
NO
YES