题目大意：

给定 $n$ 个字符串，其中字符串中的 * 可以替换任意长度的字符串，询问是否能够满足 $n$ 个字符串完全相等。

多测，$T=10,n\le 10^5$。

题目分析：

先给出一个本题优美的结论：

• 如果所有字符串都有 *，那么只需要保证前缀和后缀不冲突。
• 如果存在一个字符串没有 *，那么要求其他字符串都能和这个匹配。

如何证明？首先如果字符串都有 *，那么字符串第一个 * 和最后一个 * 之间的内容一定可以匹配（相当于是 $S_1$ 中和 $S_2$ 不匹配的用 * 强制匹配，$S_2$ 中和 $S_1$ 不匹配的用 * 强制匹配。)

如果存在一个字符串中没有 *，意味着它不可拓展，就只能被迫通过修改其它字符串来满足完全相等。

然后都不存在 * 的情况就更简单了，直接判断就行。

我们发现上面的过程在大量判断字符串是否相等，可以使用 Hash 算法优化。

具体实现可以参考代码，注意细节。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 7, K = 1e7 + 7, P = 131, M = 1e9 + 7;
int pre[2][K], lx[N], rx[N], pw[K], p[N], T;
int calc(int o, int l, int r) { return (pre[o][r] + M - pw[r - l + 1] * pre[o][l - 1] % M) % M; }
bool cmpl(int x, int y) { return lx[x] < lx[y]; }
bool cmpr(int x, int y) { return rx[x] < rx[y]; }
string s, a[N], b[N];
bool solve() {
    int n, m = 0, na = 0, nb = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> s, m = max(m, (int)s.size()), s = "#" + s;
        bool flag = 0;
        for (auto c : s)
            if (c == '*') { flag = 1;break;}
        // 统计出包含 * 的字符串的前后缀
        if (flag) {
            a[++na] = s, m = s.size() - 1, lx[na] = rx[na] = 0;
            while (s[lx[na] + 1] != '*') ++lx[na];
            while (s[m - rx[na]] != '*') ++rx[na];
        } else b[++nb] = s;
    }
    // 存在没有 * 字符串
    if (nb) {
        for (int i = 2; i <= nb; ++i)
            if (b[i] != b[1]) return 0;
        s = b[1], n = s.size() - 1;
        for (int i = 1; i <= n; ++i) pre[0][i] = (pre[0][i - 1] * P % M + s[i]) % M;
        for (int i = 1; i <= na; ++i) {
            m = a[i].size() - 1;
            for (int j = 1; j <= m; ++j) pre[1][j] = (pre[1][j - 1] * P % M + a[i][j]) % M;
            int l = 1, r = 1, j = 1;
            while (l <= m) {
                while (l <= m && a[i][l] == '*') ++l, ++r;
                if (l > m) break;
                while (r < m && a[i][r + 1] != '*') ++r;
                while (j + r - l <= n && calc(0, j, j + r - l) != calc(1, l, r)) ++j;
                if (j + r - l > n || (l == 1 && j > 1) || (r == m && calc(0, n - r + l, n) != calc(1, l, r))) return 0;
                j += r - l + 1, l = ++r;
            }
        }
    } else {
        // 全部都有 * 的字符串
        n = na, s = "#";
        for (int i = 1; i <= n; ++i) p[i] = i;
        sort(p + 1, p + n + 1, cmpl);
        for (int i = 1; i <= n; ++i) {
            int j = 1;
            while (j < (int)s.size()) {
                if (a[p[i]][j] != s[j]) return 0;
                ++j;
            }
            while (j <= lx[p[i]]) s += a[p[i]][j++];
        }
        s = "#";
        sort(p + 1, p + n + 1, cmpr);
        for (int i = 1; i <= n; ++i) {
            int j = 1, m = a[p[i]].size() - 1;
            while (j < (int)s.size()) {
                if (a[p[i]][m - j + 1] != s[j]) return 0;
                ++j;
            }
            while (j <= rx[p[i]]) s += a[p[i]][m - (j++) + 1];
        }
    }
    return 1;
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    pw[0] = 1;
    for (int i = 1; i <= 1e7; ++i) pw[i] = pw[i - 1] * P % M;
    cin >> T;
    while (T--) cout << (solve() ? "Y" : "N") << endl;
    return 0;
}