A. Spring Couplets
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Spring Festival 2022 is coming. Vingying can't hold back his excitement and starts to prepare the spring couplets.

A spring couplet is a pair of lines of poetry that adhere to specific rules. They can be seen on doorways in Chinese communities, displayed as part of the Spring Festival. The text of the couplets is often traditional and contains hopes for prosperity.

A spring couplet needs to meet various rules. For example, both lines must have the same number of Chinese characters, and the meanings of the two lines must be related, and so on. Here, we only focus on the tonal rules.

As we know, there are four primary tones of Chinese characters: flat ($$$\bar{a}$$$), rising ($$$\acute{a}$$$), falling-rising ($$$\check{a}$$$), and falling ($$$\grave{a}$$$). These can be categorized into two tone patterns: level tones and oblique tones. In detail, the flat tone and rising tone belong to level tones, and the falling-rising tone and falling tone belong to oblique tones.

A spring couplet must adhere to the following tonal rules:

  • The tone pattern of one line must be the inverse of the other. It means if one character is of a level tone, its corresponding character in the other line must be of an oblique tone, and vice versa.
  • The last character of the first line should be of an oblique tone, which forces the last character of the second line to be of a level tone.

Due to Vingying's creative mind, he creates $$$T$$$ couplets instantly. He wants to know whether each couplet adheres to the tonal rules.

Input

The first line of the input contains an integer $$$T$$$ ($$$1\le T\le 100$$$), indicating the number of couplets.

For each couplet, the first line contains an integer $$$n$$$ ($$$1\le n\le 20$$$), indicating the number of Chinese characters for each line.

For the next two lines, each line contains $$$n$$$ strings, each of which represents a Chinese character. Each string consists of lowercase letters, indicating the spelling of the Chinese character, followed by a digital number $$$1$$$ (flat), $$$2$$$ (rising), $$$3$$$ (falling-rising), or $$$4$$$ (falling) representing the tone.

It is guaranteed that the length of each string is no more than $$$7$$$ and no less than $$$2$$$.

Output

For each couplet, if it adheres to the tonal rules, print YES in a single line. Otherwise, print NO in a single line.

Example
Input
4
7
qian1 men2 wan3 hu3 tong2 tong2 ri4
zong3 ba3 xin1 tao2 huan4 jiu4 fu2
7
ping2 ping2 ze4 ze4 ping2 ping2 ze4
ze4 ze4 ping2 ping2 ze4 ze4 ping2
7
gou3 li4 guo2 jia1 sheng1 si3 yi3
qi3 yin1 huo4 fu2 bi4 qu1 zhi1
3
nun1 heh1 heh1
a4 a4 a4
Output
YES
YES
NO
NO
Note

For the third example, the tones of the first character do not adhere to the rule, as they are both oblique tones.

For the fourth example, the tones of the last character do not adhere to the rule, as the last character in the first line is not of an oblique tone.