//Tran Thuy Duong
#include <bits/stdc++.h>
#define task ""
#define maxn 100005
#define maxs 400005
#define MOD 1000000007
#define pii pair<int, int>
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define reset(x) memset(x, 0, sizeof x)

using namespace std;
typedef long long ll;
const ll MM = 1ll * MOD * MOD;

int n, q, dem = 0;
string s[maxn];
int Child[maxs][26], dd[maxs], val[maxs];

void Add(string st, int id)
{
    int node = 0;
    for (int c, i=0; i<st.length(); i++)
    {
        c = st[i] - 'a';
        if (Child[node][c] == 0) Child[node][c] = ++dem;
        node = Child[node][c];
        val[node]++;
    }
    dd[node] = id;
}

int tmp[26][26], sstr = 0, sub[maxn];
int cnt[maxn][26][26];
void DFS(int u)
{
    int node;
    for (int c=0; c<='z'-'a'; c++)
    {
        if (Child[u][c] == 0) continue;
        node = Child[u][c];
        for (int x=0; x<='z'-'a'; x++)
            tmp[c][x] += val[Child[u][x]];
        if (dd[node])
        {
            int id = dd[node];
            sub[id] = sstr;
            for (int x=0; x<='z'-'a'; x++)
                for (int y=0; y<='z'-'a'; y++)
                    cnt[id][x][y] = tmp[x][y];
        }
        sstr += (dd[node] != 0);
        DFS(node);
        sstr -= (dd[node] != 0);
        for (int x=0; x<='z'-'a'; x++)
            tmp[c][x] -= val[Child[u][x]];
    }
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	//freopen(task".INP", "r", stdin);
	//freopen(task".OUT", "w", stdout);
    cin >> n;
    for (int i=1; i<=n; i++)
    {
        cin >> s[i];
        Add(s[i], i);
    }
    DFS(0);

    int k, ans, x, y;
    string p;
    cin >> q;
    while (q--)
    {
        cin >> k >> p;
        ans = 0;
        for (int i=0; i<p.length(); i++)
            for (int j=0; j<i; j++)
            {
                x = p[i] - 'a'; y = p[j] - 'a';
                ans += cnt[k][x][y];
            }
        cout << ans + sub[k] + 1 << "\n";
    }
	return 0;
}

### Prompt

Please create a solution in cpp to the following problem:

There are N strings of lowercase alphabet only. The i-th string is S_i. Every string is unique.

Provide answers for the Q queries below. The i-th query has the following format:

Query: An integer k_i and a string p_{i,1}p_{i,2}...p_{i,26} that results from permuting {`a`,`b`,...,`z`} are given. Output the sequence of the string S_{k_i} among the N strings in lexicographical order when the literal sequence is p_{i,1}<p_{i,2}<...<p_{i,26}.

Constraints

* 1 ≦ N,Q ≦ 100000
* 1 ≦ |S_i| (1 ≦ i ≦ N)
* S_i (1 ≦ i ≦ N) is a string of lowercase alphabet.
* The sum of |S_i| is no more than 400000.
* Every S_i is unique.
* 1 ≦ k_i ≦ N (1 ≦ i ≦ Q)
* For all 1 ≦ i ≦ Q, p_{i,1}p_{i,2}...p_{i,26} is a permutation of `abcd...z`.

Input

Inputs are provided from standard inputs in the following form.


N
S_1
:
S_N
Q
k_1 p_{1,1}p_{1,2}...p_{1,26}
:
k_Q p_{Q,1}p_{Q,2}...p_{Q,26}


Output

Output Q lines.

On line i, for the i-th query, output an integer indicating the sequence of the string S_{k_i} among the N strings in lexicographical order.

Examples

Input

5
aa
abbaa
abbba
aaab
aaaaaba
5
1 abcdefghijklmnopqrstuvwxyz
2 bacdefghijklmnopqrstuvwxyz
3 abcdefghijklmnopqrstuvwxyz
4 bacdefghijklmnopqrstuvwxyz
5 abcdefghijklmnopqrstuvwxyz


Output

1
2
5
4
2


Input

8
abrakatabra
abadaba
abracadabra
atcoder
grand
contest
ababa
a
6
3 abcdefghijklmnopqrstuvwxyz
6 qwertyuiopasdfghjklzxcvbnm
8 poiuytrewqlkjhgfdsamnbvcxz
2 qazwsxedcrfvtgbyhnujmikolp
1 plokmijnuhbygvtfcrdxeszwaq
4 mnbvcxzasdfghjklpoiuytrewq


Output

4
8
2
3
4
7

### Response

```cpp
//Tran Thuy Duong
#include <bits/stdc++.h>
#define task ""
#define maxn 100005
#define maxs 400005
#define MOD 1000000007
#define pii pair<int, int>
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define reset(x) memset(x, 0, sizeof x)

using namespace std;
typedef long long ll;
const ll MM = 1ll * MOD * MOD;

int n, q, dem = 0;
string s[maxn];
int Child[maxs][26], dd[maxs], val[maxs];

void Add(string st, int id)
{
    int node = 0;
    for (int c, i=0; i<st.length(); i++)
    {
        c = st[i] - 'a';
        if (Child[node][c] == 0) Child[node][c] = ++dem;
        node = Child[node][c];
        val[node]++;
    }
    dd[node] = id;
}

int tmp[26][26], sstr = 0, sub[maxn];
int cnt[maxn][26][26];
void DFS(int u)
{
    int node;
    for (int c=0; c<='z'-'a'; c++)
    {
        if (Child[u][c] == 0) continue;
        node = Child[u][c];
        for (int x=0; x<='z'-'a'; x++)
            tmp[c][x] += val[Child[u][x]];
        if (dd[node])
        {
            int id = dd[node];
            sub[id] = sstr;
            for (int x=0; x<='z'-'a'; x++)
                for (int y=0; y<='z'-'a'; y++)
                    cnt[id][x][y] = tmp[x][y];
        }
        sstr += (dd[node] != 0);
        DFS(node);
        sstr -= (dd[node] != 0);
        for (int x=0; x<='z'-'a'; x++)
            tmp[c][x] -= val[Child[u][x]];
    }
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	//freopen(task".INP", "r", stdin);
	//freopen(task".OUT", "w", stdout);
    cin >> n;
    for (int i=1; i<=n; i++)
    {
        cin >> s[i];
        Add(s[i], i);
    }
    DFS(0);

    int k, ans, x, y;
    string p;
    cin >> q;
    while (q--)
    {
        cin >> k >> p;
        ans = 0;
        for (int i=0; i<p.length(); i++)
            for (int j=0; j<i; j++)
            {
                x = p[i] - 'a'; y = p[j] - 'a';
                ans += cnt[k][x][y];
            }
        cout << ans + sub[k] + 1 << "\n";
    }
	return 0;
}

```