在本题中，所有字符串仅由四个字符组成：a, b, c 和 d。

Busy Beaver 有三个他非常害怕的字符串 $x, y$ 和 $z$。特别地，他只喜欢那些不是这三个字符串中任何一个的子序列*的字符串。

回答 $Q$ 个询问。在第 $i$ 个询问中，给定一个字符串 $s_i$，使得 $x, y$ 和 $z$ 均为 $s_i$ 的子序列，且 $|s_i| > \max(|x|, |y|, |z|)$。请帮助 Busy Beaver 找到 $s_i$ 的最短子序列，且该子序列不是 $x, y$ 或 $z$ 中任何一个的子序列。

输入格式

输入的前三行包含字符串 $x, y$ 和 $z$ ($1 \le |x|, |y|, |z| \le 60$)，由字符 a, b, c, d 组成。

下一行包含一个正整数 $Q$ ($1 \le Q \le 1.5 \cdot 10^5$)。

接下来的 $Q$ 行，每行包含一个字符串，第 $i$ 个字符串为 $s_i$ ($\max(|x|, |y|, |z|) < |s_i| \le 3 \cdot 10^5$)，由字符 a, b, c, d 组成，且满足 $s_i$ 包含 $x, y$ 和 $z$ 作为子序列。

所有询问中 $|s_i|$ 的总和不超过 $3 \cdot 10^5$。

输出格式

在第 $i$ 行，输出一个正整数，表示 $s_i$ 的最短子序列的长度，且该子序列不是 $x, y$ 或 $z$ 中任何一个的子序列。

样例

样例输入 1

abb
bcc
abcc
3
abcbc
dabcabc
abbcc

样例输出 1

2
1
3

说明

在第一个询问中，abcbc 的所有长度为 1 的子序列都是 $x, y$ 或 $z$ 中某一个的子序列，但子序列 cb 不是，因此答案为 2。

在第二个询问中，d 是 dabcabc 的一个子序列，且它不是 $x, y$ 或 $z$ 中任何一个的子序列。

在第三个询问中，bbc 是 abbcc 的一个子序列，且它不是 $x, y$ 或 $z$ 中任何一个的子序列，同时它是满足条件的最短子序列。

*如果一个字符串 $s$ 可以通过从字符串 $t$ 中删除若干个（可能为零个或全部）字符，且不改变剩余字符的相对顺序而得到，则称 $s$ 是 $t$ 的子序列。