The ancient civilization of the Prendonians, who lived in Jutland from 5000 BC to 4500

BC, is well known. A Prendonian name is composed of three non empty words formed by

lowercase letters from a to z: an unique first name, one of their parents’ fist name with a

suffix and the other parent’s name with the same suffix. The unique first name always comes

first, but there is no specific order for the other two.

The suffix denotes the gender of the bearer of the name, jk for male and gvw for female,

for example, if ric is igo and malte’s son, his full name would be ric igojk maltejk, but had

ric been a girl, his name would have been ric igogvw maltegvw.

All the Prendonians were monogamic and faithful to their partners. There are no registers

of male homosexual couples, but it was common for two women to be married, and there has

not been a single case of married siblings in Prendonian history. A couple was not considered

married until they had given birth to a child or adopted one.

Given N 3 word names, write a program that prints Y ES if they are all valid and part of

a valid Prendonian family tree and everyone is related to everyone else, print N O otherwise.

Input

The first line consists of a single integer T (1 ≤ T ≤ 30), which is the number of test

cases. Each test case begins with a line with only the integer N (1 ≤ N ≤ 1000), the number

of names, followed by N lines with 3 word (a-z lowercase only, each word not longer than 103

characters), the first word is garanteed to be unique.

Output

For each test case print YES if the names are all valid and part of a valid Prendonian

family tree and are all related to each other, print NO otherwise.

Example

Input:
1
3
docs afegvw fegvw
draw rridajk cajk
pito docsjk drawjk
Output:
YES