当出题人醒来的时候，发现自己在人里的一户人家里，家里有一个看起来像是13岁的孩童，自称是芙兰什么路来着。

她给了你一个字符串，想知道这个字符串的前后缀的性质，由于出题人刚醒，于是就请你帮帮出题人写一个程序计算罢。 （来自托尔与白渃的鼓励）

给定 n 个小写字母字符串，第 i 个字符串为 s_i。

定义一个字符串长为 k 的前缀是它的前 k 个字符组成的子串，长为 k 的后缀是它的后 k 个字符组成的子串，例如对字符串 kobayashibairuo，长为 3 的前缀为 kob，长为 5 的后缀为 airuo。

有 q 个询问，每个查询给出两个整数 x, y，你需要求出对所有 n 个字符串 s_i(1\le i\le n) 的全体非空后缀里，有多少个后缀与 s_x 的长为 y 的前缀相等。

输入一行整数 n(1 \le n \le 10^5)，代表字符串数量。

接下来输入 n 行，第 i 行输入字符串 s_i(1\le |s_i|\le 2\times 10^5)。

接下来输入一行一个整数 q(1 \le q \le 10^6)。

接下来输入 q 行，第 i 行包括两个整数 x, y(1\le x\le n,1\le y\le |s_x|)。

保证所有字符串长度之和不超过 2\times 10^5，且所有字符串仅有小写字母组成。

为了防止输出过多，请输出一行一个整数，代表每个询问的答案之和。

对第一个样例，与 s_1 长为 3 的前缀相等的只有 s_2 长为 3 的后缀。

对第二个样例，对第一个询问 c，所有 4 个长为 1 的后缀都匹配；对第二个询问 cp，没有任何一个后缀匹配。对第三个询问 cpc，所有 4 个长为 3 的后缀都匹配；答案为 4+0+4=8。