#include <bits/stdc++.h>
 
using namespace std;
 
typedef pair<string,int> P;
int N,Q,K,X,Y,W,Max,I,ans;
const int A=777777,B=223456;
const int INF=1000000009;
 
char C[A]; 
int parent[A],Parent[A],node[A],Node[A],O[30];
int G[B]; P H[B];
int J[B];
int JJ[A];
int Cnt[A];
int table[30][30]; 
vector<int> ch[A],L[A];
string S[B],T[B],U[B],V[B],R[B];
 
void dfs(int s,int e,int j,int p){
    int x=S[s][j]-'a'; int k=s;
  for(int i=s; i<=e; i++){
    if(x!=S[i][j]-'a'){
      dfs(k,i-1,j,p); k=i;
      x=S[i][j]-'a'; 
    }
  }
     //cout<<x<<" "<<j<<" "<<I++<<" "<<p<<endl;
     if(x<0) node[I]=26;
     else node[I]=x;
     if(j==0) parent[I]=A-10;
     else parent[I]=p;
     I++;
    if(x<0) return;
    if(j<Max) dfs(k,e,j+1,I-1);
    return;
}
int Pr(int k){
  int p=parent[k];
  if(p==A-10) return A-10;
  if(ch[parent[p]].size()==1){
    return Pr(p);
  }else{
    return p;
  }
}
int cnt(int k){
  if(L[k].size()==0){
    Cnt[k]=1;
    return 1;
  }
  for(int i=0; i<L[k].size(); i++){
    Cnt[k]+=cnt(L[k][i]);
  }
    return Cnt[k];
}
void make(int k){
  if(L[k].size()==0){
    J[X]=node[k]; JJ[X]=k;
    X++;
    return;
  }
  for(int i=0; i<L[k].size(); i++){
    make(L[k][i]);
  }
  return;
}
void Find(int k){
  if(W>=V[G[K-1]].size()) return;
  if(L[k].size()==0) return;
  int s;
  if(V[G[K-1]][W]-'a'>=0) s=V[G[K-1]][W]-'a'; 
  else s=-INF;
  int t;
  for(int i=0; i<L[k].size(); i++){
     if(s==node[L[k][i]]){
      t=L[k][i]; 
     }
     if(node[L[k][i]]<26&&table[s][node[L[k][i]]]==0){
      ans+=Cnt[L[k][i]];
     }
     if(node[L[k][i]]==26){
      ans++;
      Find(L[k][i]); 
     }
  }
  W++; Find(t); 
  return;
}
 
int main(){
 
cin>>N; 

for(int i = 0; i < N; i++){
  scanf("%s", C);
  S[i] = string(C);
  if(S[i].size()>Max) Max=S[i].size();
}

if(N>1){
 
for(int i = 0; i < N; i++) U[i]=S[i];
 
sort(S,S+N);
 
dfs(0,N-1,0,A-10);  
 
for(int i = 0; i < I; i++) ch[parent[i]].push_back(i);
 
for(int i = 0; i < I; i++){
  int p=parent[i];
  if(ch[p].size()==1) node[i]=-INF;
}
 
for(int i = 0; i < I; i++){
  if(node[i]!=-INF){
    Parent[i]=Pr(i);
  }else{
    Parent[i]=-INF;
  }
}
 
for(int i = 0; i < I; i++){
  if(Parent[i]>=0) L[Parent[i]].push_back(i);
}
 
make(A-10); 
for(int i=0; i<N; i++){
  if(J[i]<=25){
    char c='a'+J[i];
    V[i]=c;
  }
  if(J[i]==26){
    V[i]="";
  }
  int k=JJ[i];
  while(1){
    if(Parent[k]==A-10) break;
    char c='a'+node[Parent[k]];
    V[i]=c+V[i];
    k=Parent[k];
  }
}
 
sort(V,V+N); 
for(int i=0; i<N; i++){
  H[i].first=U[i];
  H[i].second=i;
}
sort(H,H+N);
for(int i=0; i<N; i++){
  G[H[i].second]=i;
}
 
cnt(A-10);

}
 
cin>>Q;
 
for(int i=0; i<Q; i++){
  scanf("%d %s",&K,C);
  T[i] = string(C);
  for(int j=0; j<26; j++){
    O[T[i][j]-'a']=j;
  }
 for(int k=0; k<26; k++){
  for(int j=0; j<26; j++){
    table[k][j]=0;
  }
 }
 for(int k=0; k<26; k++){
  for(int j=0; j<26; j++){
   if(O[k]<=O[j]){
    table[k][j]=1;
   }else{
    table[k][j]=0;
   }
  }
 }
  X=0; I=0; ans=0; W=0;
  if(N==1) printf("%d\n",1);
  else{ 
    Find(A-10);
    printf("%d\n",ans+1);
  }
}
 
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
#include <bits/stdc++.h>
 
using namespace std;
 
typedef pair<string,int> P;
int N,Q,K,X,Y,W,Max,I,ans;
const int A=777777,B=223456;
const int INF=1000000009;
 
char C[A]; 
int parent[A],Parent[A],node[A],Node[A],O[30];
int G[B]; P H[B];
int J[B];
int JJ[A];
int Cnt[A];
int table[30][30]; 
vector<int> ch[A],L[A];
string S[B],T[B],U[B],V[B],R[B];
 
void dfs(int s,int e,int j,int p){
    int x=S[s][j]-'a'; int k=s;
  for(int i=s; i<=e; i++){
    if(x!=S[i][j]-'a'){
      dfs(k,i-1,j,p); k=i;
      x=S[i][j]-'a'; 
    }
  }
     //cout<<x<<" "<<j<<" "<<I++<<" "<<p<<endl;
     if(x<0) node[I]=26;
     else node[I]=x;
     if(j==0) parent[I]=A-10;
     else parent[I]=p;
     I++;
    if(x<0) return;
    if(j<Max) dfs(k,e,j+1,I-1);
    return;
}
int Pr(int k){
  int p=parent[k];
  if(p==A-10) return A-10;
  if(ch[parent[p]].size()==1){
    return Pr(p);
  }else{
    return p;
  }
}
int cnt(int k){
  if(L[k].size()==0){
    Cnt[k]=1;
    return 1;
  }
  for(int i=0; i<L[k].size(); i++){
    Cnt[k]+=cnt(L[k][i]);
  }
    return Cnt[k];
}
void make(int k){
  if(L[k].size()==0){
    J[X]=node[k]; JJ[X]=k;
    X++;
    return;
  }
  for(int i=0; i<L[k].size(); i++){
    make(L[k][i]);
  }
  return;
}
void Find(int k){
  if(W>=V[G[K-1]].size()) return;
  if(L[k].size()==0) return;
  int s;
  if(V[G[K-1]][W]-'a'>=0) s=V[G[K-1]][W]-'a'; 
  else s=-INF;
  int t;
  for(int i=0; i<L[k].size(); i++){
     if(s==node[L[k][i]]){
      t=L[k][i]; 
     }
     if(node[L[k][i]]<26&&table[s][node[L[k][i]]]==0){
      ans+=Cnt[L[k][i]];
     }
     if(node[L[k][i]]==26){
      ans++;
      Find(L[k][i]); 
     }
  }
  W++; Find(t); 
  return;
}
 
int main(){
 
cin>>N; 

for(int i = 0; i < N; i++){
  scanf("%s", C);
  S[i] = string(C);
  if(S[i].size()>Max) Max=S[i].size();
}

if(N>1){
 
for(int i = 0; i < N; i++) U[i]=S[i];
 
sort(S,S+N);
 
dfs(0,N-1,0,A-10);  
 
for(int i = 0; i < I; i++) ch[parent[i]].push_back(i);
 
for(int i = 0; i < I; i++){
  int p=parent[i];
  if(ch[p].size()==1) node[i]=-INF;
}
 
for(int i = 0; i < I; i++){
  if(node[i]!=-INF){
    Parent[i]=Pr(i);
  }else{
    Parent[i]=-INF;
  }
}
 
for(int i = 0; i < I; i++){
  if(Parent[i]>=0) L[Parent[i]].push_back(i);
}
 
make(A-10); 
for(int i=0; i<N; i++){
  if(J[i]<=25){
    char c='a'+J[i];
    V[i]=c;
  }
  if(J[i]==26){
    V[i]="";
  }
  int k=JJ[i];
  while(1){
    if(Parent[k]==A-10) break;
    char c='a'+node[Parent[k]];
    V[i]=c+V[i];
    k=Parent[k];
  }
}
 
sort(V,V+N); 
for(int i=0; i<N; i++){
  H[i].first=U[i];
  H[i].second=i;
}
sort(H,H+N);
for(int i=0; i<N; i++){
  G[H[i].second]=i;
}
 
cnt(A-10);

}
 
cin>>Q;
 
for(int i=0; i<Q; i++){
  scanf("%d %s",&K,C);
  T[i] = string(C);
  for(int j=0; j<26; j++){
    O[T[i][j]-'a']=j;
  }
 for(int k=0; k<26; k++){
  for(int j=0; j<26; j++){
    table[k][j]=0;
  }
 }
 for(int k=0; k<26; k++){
  for(int j=0; j<26; j++){
   if(O[k]<=O[j]){
    table[k][j]=1;
   }else{
    table[k][j]=0;
   }
  }
 }
  X=0; I=0; ans=0; W=0;
  if(N==1) printf("%d\n",1);
  else{ 
    Find(A-10);
    printf("%d\n",ans+1);
  }
}
 
return 0;
 
}
```