Description

One day, a bored Xiao L started playing the currently popular game Hearthstone, but he kept losing. He shouted, “I’m going to copy a decklist!” and went to watch the livestream of top Legend player Xiao H.

However, Xiao L’s internet is still stuck in the dial-up era. The livestream is laggy and garbled, and his poor connection makes it impossible to record the full powerful decklist Xiao H shows. No one around Xiao L plays games, but they are all top students who love discussing informatics problems.

So he came up with an idea: since each garbled frame appears in different positions on the screen, Xiao L can record some parts of the decklist each time. If he records many times, maybe he can reconstruct a decklist Xiao L wants.

But there’s a problem: the decklist Xiao H shows each time might be different. So he wants to know whether the decklist fragments he copied each time are consistent.

Abstracted as an academic problem for you to solve: the wildcard * matches a string of any length (including $0$). Determine whether all the strings are pairwise matching.

Input Format

The first line contains a positive integer $T$, the number of test cases.

Then follow $T$ test cases:
For each test case, the first line contains a positive integer $N$, the number of strings in this test case.
Then follow $N$ lines, each containing one string. Each string consists only of lowercase letters, digits, and the wildcard symbol *.

Note: The testdata is in UNIX format and may contain blank lines. You may read the input character by character.

Output Format

Output $T$ lines, each containing a single letter Y or N. Y means all strings in this test case are pairwise matching, and N means there exists at least one pair of strings that do not match.

10
2
1234567890*1234567890
1234567890a1234567890
2
1234567890*1234567890
1234567890*1234567890
2
1234*67890a1234567890
1234567890*1234567890
2
1234567890*1234567890
1234567890a12345*7890
2
1234567890*1234567890
*12345
2
12345*67890
1234567890*1234567890
2
1234567890*1234567890
12345*
2
1234567890*1234567890
*67890
2
67890*
1234567890*1234567890
2
1234567890*a*1234567890
1234567890*1234567890

Y
Y
Y
Y
N
Y
Y
Y
N
Y

Hint

For $100\%$ of the testdata, $N \leq 100000$, $T = 10$, the input file size does not exceed $10\text{M}$, and $N \times$ the longest string length does not exceed $2 \times 10^8$.

Currently, only in hack testdata, $T = 1$.

Translated by ChatGPT 5