问题描述

小杨有 n 个仅包含小写字母的字符串 s₁, s₂, ..., s_n，想将这些字符串按一定顺序排列后拼接成一个字符串 t，使得对于所有的 j < i，均有 t_j ≤ t_i（字符大小关系与字母表顺序一致，如 e < g < p < s）。请判断是否存在满足条件的字符串排列顺序。

格式

• ​输入​：第一行包含一个正整数 T，代表测试数据组数。 对于每组测试数据，第一行包含一个正整数 n。之后 n 行，每行包含一个字符串 s_i。
• ​输出​：对于每组测试数据，如果存在满足条件的排列顺序，输出 1，否则输出 0。

样例

3
3
aa
ac
de
2
aac
bc
1
gesp

1
0
0

提示

数据范围：保证 1 ≤ T, n ≤ 100，每个字符串的长度不超过 10。