Alice 制造了一些可以生成字符串的机器。每台机器由 $N$ 个状态组成，编号从 1 到 $N$，状态之间有一组有向边，每条边都标有一个来自固定字符集的字符。状态的一个子集被称为“终止”状态。机器通过以下方式生成字符串：从状态 1 开始，沿着一条路径移动，直到到达一个终止状态，并将路径上经过的边的标签按顺序连接起来。路径可以多次访问同一个状态，也可以多次经过同一条边。路径可以在最终终止于某个终止状态之前经过其他终止状态。允许存在自环，也允许存在两条或多条从同一状态出发或到达同一状态且标签相同的边。

Bob 有一个最喜欢的字符串 $S$，Carol 有一个最喜欢的字符串 $T$。Alice 想知道她是否能制造出一台机器，使其生成的字符串恰好是那些包含 $S$ 和 $T$ 的出现次数相等的字符串。也就是说，该机器应该生成每一个包含 $S$ 和 $T$ 出现次数相等的字符串，且不应生成任何不满足此属性的字符串。字符串的出现可以重叠。例如，字符串 banana 中子串 ana 出现了两次。请帮助 Alice 确定是否可以为 Bob 和 Carol 最喜欢的字符串完成这项任务。

图 H.1：样例输入中第一个案例的示例机器。

图 H.1 展示了样例输入中第一个案例的示例机器。方形状态表示终止状态。

输入格式

输入的第一行包含一个正整数 $K$ ($1 \le K \le 50$)，表示测试用例的数量。接下来有 $K$ 行，每行包含三个字符串 $A, S, T$。第一个字符串 $A$ 是机器中使用的固定字符集。$A$ 中的字符是互不相同的英文小写字母。第二个字符串 $S$ 是 Bob 最喜欢的字符串。第三个字符串 $T$ 是 Carol 最喜欢的字符串。$S$ 和 $T$ 的长度满足 $1 \le |S|, |T| \le 500$。保证 $S$ 和 $T$ 中出现的不同字符是 $A$ 中字符的子集。

输出格式

对于每个测试用例，输出一行。如果 Alice 可以按照描述制造出机器，则输出 1，否则输出 0。

样例

样例输入 1

3
ab ab ba
abc ab ba
cz cczz zzcc

样例输出 1

1
0
0