给定两个字符串 $a$ 和 $b$。

如果字符串 $s$ 可以通过从字符串 $t$ 的开头删除若干个（可以为零个）字符，并从末尾删除若干个（可以为零个）字符得到，则称 $s$ 是 $t$ 的子串。特别地，空串是任何字符串的子串。

给定 $q$ 个询问字符串。对于长度为 $m$ 的询问字符串 $c$，以及从 $1$ 到 $m$ 的每个 $k$，统计满足以下条件的不同字符串 $x$ 的个数：

• $x$ 是 $a$ 的子串；
• $xc_1c_2\ldots c_k$ 是 $b$ 的子串。

字符串 $x$ 可以为空。只要两个字符串 $x$ 的内容相等，就将它们视为相同的字符串，无论它们出现在 $a$ 的哪个位置。

输入格式

第一行包含一个整数 $t$（$1\le t\le 10^4$），表示测试用例的数量。

每个测试用例的第一行包含字符串 $a$（$1\le |a|\le 150\,000$）。

第二行包含字符串 $b$（$1\le |b|\le 150\,000$）。

第三行包含一个整数 $q$（$1\le q\le 150\,000$），表示询问的数量。

接下来的 $q$ 行每行包含一个询问字符串 $c$（$1\le |c|\le 150\,000$）。

所有字符串均由小写英文字母组成。

保证所有测试用例的 $|a|$ 之和不超过 $150\,000$，所有测试用例的 $|b|$ 之和不超过 $150\,000$，且所有测试用例中所有询问字符串的 $|c|$ 之和不超过 $150\,000$。

输出格式

对于每个询问，输出 $|c|$ 个整数：其中第 $k$ 个整数应为满足 $x$ 是 $a$ 的子串且 $xc_1c_2\ldots c_k$ 是 $b$ 的子串的不同字符串 $x$ 的个数。

样例

输入格式 1

4
ab
cababa
5
a
b
ab
ba
c
aaa
aaaaa
4
a
aa
aaa
aaaa
abc
xyz
4
a
xy
z
abc
banana
anaban
5
a
na
an
ban
n

输出格式 1

3
2
3 3
2 2
1
4
4 4
4 4 3
4 4 3 2
0
1 1
1
0 0 0
4
3 2
4 2
4 4 4
3

输入格式 2

1
ab
aaba
1
ab

输出格式 2

4 2

说明

在第二个样例中，对于前缀 a，四个合法的字符串 $x$ 分别为空串、a、b 和 ab。特别地，虽然 a 和 b 的长度相同，但它们都必须计入。对于完整的询问字符串 ab，只有空串和 a 合法。