题目描述

给定 $n$ 个非空小写英文字母字符串，以及 $m$ 次询问。

每次询问给出两个非空字符串 $p$ 和 $s$，你需要回答：给定的 $n$ 个字符串中，有多少个字符串同时满足：

• 以 $p$ 为前缀；
• 以 $s$ 为后缀。

输入格式

第一行一个整数 $n$，表示字符串数量。

接下来 $n$ 行，每行一个非空字符串，仅由小写英文字母 a 到 z 组成。

接下来一行一个整数 $m$，表示询问数量。

接下来 $m$ 行，每行两个由一个空格分隔的非空字符串 $p$ 和 $s$，分别表示要求的前缀和后缀。

数据范围：

• 所有给定字符串的总长度不超过 $100000$；
• 所有询问中的前缀长度之和与后缀长度之和不超过 $200000$；
• 所有字符串均只包含小写英文字母。

输出格式

输出 $m$ 行。

第 $i$ 行输出一个整数，表示第 $i$ 次询问的答案。

样例

3
aaaaa
abacabaa
avtobus
6
a a
a aa
aa a
aaaaa aaaa
abac caba
abac a

2
2
1
1
0
1