Chandelier is a type of lamp, that is defined recursively: it is composed of a round frame with a few hooks (one or more), and on each hook there is either a colourful lightbulb, or another chandelier hanging from it. Your task is very simple: given description of two chandeliers, decide if they are identical or not. Of course, since frames are round, only the cyclic order of items in each frame matters.

Input

On the first line of input, there is integer T, 1 \le T \le 100, denoting number of tests. T testcases follow, each describing two chandeliers.
Each chandelier is described recursively, starting with d, the size of the root chandelier, and then:

• If d>0, it is a frame with d slots, and d description of chandeliers hanging below this one follow, provided in counter-clockwise order.
• If d=0, it is a lightbulb, and then a single lowercase letter of alphabet follows, describing the colour of the lightbulb.

Output

For each test, output YES or NO, depending whether two described chandeliers are identical.

Example 1

Input:

1
3 3 0 a 0 b 0 c 3 0 d 0 e 0 f 3 0 a 0 b 0 c
3 3 0 c 0 a 0 b 3 0 a 0 b 0 c 3 0 e 0 f 0 d

Output:

YES

Example 2

Input:

1
3 0 a 0 b 0 c
3 0 c 0 b 0 a

Output:

NO

Limits:

In total, the number of chandeliers and lightbulbs does not exceed N, and for each frame, number of slots do not exceed D.

• first group of tests: N = 1000 and D = 2.
• second group of tests: N = 10000 and D = 10.
• third group of tests: N,D = 10000.