P17374 [ECNA 2023] Impartial Strings

Alice 会制造生成字符串的机器。她制造的每台机器都包含 $N$ 个状态，编号为 $1$ 到 $N$；状态之间还有若干条有向边，每条边都标有固定字符集合中的一个字符。部分状态是“终止状态”。 机器生成字符串的过程如下：从状态 $1$ 出发，沿一条最终终止于某个终止状态的路径行走，并按照经过各条边的顺序，将边上的字符标签依次连接起来。路径可以多次访问同一个状态，也可以多次经过同一条边；还可以在最终停在某个终止状态之前先经过其他终止状态。机器允许有自环，也允许存在两条或更多标有同一字符、且指向同一状态和／或从同一状态出发的边。 Bob 最喜欢的字符串是 $S$，Carol 最喜欢的字符串是 $T$。Alice 想知道，她能否制造一台机器，使其生成的字符串恰好是那些以子串形式出现的 $S$ 与 $T$ 次数相等的字符串。也就是说，这台机器必须生成所有满足该性质的字符串，同时不能生成任何不满足该性质的字符串。 子串的出现位置可以重叠。例如，字符串 `banana` 中子串 `ana` 出现了两次。请帮助 Alice 判断，对于 Bob 和 Carol 最喜欢的字符串，她能否完成这项任务。 图 1 给出了样例输入中第一组数据对应的一台机器。方形状态表示终止状态。 :::align{center}  :::

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

每组测试用例输出一行。如果 Alice 能够制造出上述机器，输出 $1$；否则输出 $0$。