Pairwise Wildcard Matching

You are given a set of string patterns. Each pattern is composed of lowercase letters and the wildcard character $*$, which can match any sequence of characters (including the empty sequence). Determine whether there exists a string that matches all of the given patterns. Equivalently, check if every two patterns are compatible (i.e. they have a non‐empty intersection).

Note: The wildcard character $*$ can match any sequence (even an empty one).

inputFormat

The first line of the input contains an integer T, representing the number of test cases. Each test case begins with an integer n, the number of patterns. Then n lines follow, each containing a pattern string consisting of lowercase letters and the wildcard character *.

For example:

3
*abc
a*
*abc*

outputFormat

For each test case, print a single line: Yes if there exists a string that matches all the given patterns, or No otherwise.

sample

3
*abc
a*
*abc*

Yes