当且仅当字符串 $A$ 在字符串 $B$ 的位置 $i$ 处出现，或者存在一个字符串 $A'$（由 $A$ 在某一个位置替换为另一个字母得到），使得 $A'$ 在 $B$ 的位置 $i$ 处出现时，我们称字符串 $A$ 在字符串 $B$ 的位置 $i$ 处出现且至多有一个错误。

给定一个字符串 $T$ 和一系列查询。对于每个查询字符串，你需要计算它在 $T$ 中出现且至多有一个错误的位置数量。

输入格式

输入的第一行包含测试用例的数量 $z$。接下来是各测试用例的描述。

每个测试用例的第一行包含一个长度在 $1$ 到 $200\,000$ 之间、由小写拉丁字母组成的字符串 $T$。下一行包含一个整数 $q$，表示查询的数量。接下来的 $q$ 行，每行包含一个由小写拉丁字母组成的非空字符串，即一个查询。单个测试用例中所有查询的长度之和不超过 $200\,000$。

所有测试用例中出现的字符串总长度（包括查询）不超过 $1\,200\,000$。

输出格式

对于每个查询，输出该查询在 $T$ 中出现且至多有一个错误的位置数量。

样例

输入 1

1
abcdefghij
2
abd
a

输出 1

1
10