Morphic is a tree that grows very rapidly, bringing happiness to its owner. It has a single trunk consisting of a number of cells stacked one on top of another. Each cell has one of n possible colors which determine the way it mutates during the night, while nobody can see it. Florists denote these colors by the first n small letters of the English alphabet and know exactly into how many cells, and of what colors, a cell of each color divides. In fact, they have wrote their knowledge down simply with n nonempty words, each word representing the resulting sequence of colors.

A seed of a Morphic has a single cell of color a and is rooted firmly in the ground. As long as the Morphic is still alive, each night all its cells simultaniously morph according to the aforementioned rules, possibly causing an exponential growth because each new cell is of the same size as the original one. For example, if rules say that a becomes ab, and b becomes ca, then after two nights a seed will evolve to a trunk consisting of 4 cells: abca.

Therefore the top of a Morphic is usually hidden in clouds. The only way to tell if it is still alive is to check if visible part of the trunk is changing colors. In order to do so, one can build enormously high (yet still of constant height) tower, and watch from its top a fixed fragment of the trunk.

As you can easily see, it is either sufficient to observe first k cells from the bottom for some fixed k, or no matter how high the tower is, you will not be able to tell for sure if a Morphic died. The latter happens when for every k, rules cause the k-th cell to eventually stop changing colors, even though the tree is still alive and mutating.

To prevent waste of money on building such enormous towers, you are to write a program that determines if it is possible to monitor health of a Morphic.

Input

The input contains several Morphics descriptions. The first line contains the number of descriptions t (t <= 10000) that follow. Each of them begins with the number of colors n (1 <= n <= 26). Next n lines contain the rules by which the Morphic grows. The i-th one describes the sequence of colors in bottom-up order obtained from a single cell of i-th color. Each line contains at most 100 lowercase English letters.

Output

For each test case output one line containing YES if building of a tower is pointless (as in: YES, we can save money!). Otherwise output NO.

Example

Input:
4
2
ab
a
3
ba
c
c
3
ba
c
b
3
bbbbbbbbbbbbbbb
ccccccccccccccc
c
Output:
YES
YES
NO
YES