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 YES if they are all valid and part of a valid Prendonian family tree and everyone is related to everyone else, print NO 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 guaranteed 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