#include <iostream>
#include <fstream>
#include <cassert>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#include <time.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,string> pip;
typedef vector<pip> vip;
const int inf=2*1e9+1;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

class Trie{
	private:
	const int MAX=400005;
	int ID=1;
	vvi date;
	vi u,v;
	public:
	Trie(){
		date=vvi(MAX,vi(26,-1));
		u=v=vi(MAX);
	}
	void Update(string s){
		int S=s.size(),I=0;
		for(int i=0;i<S;i++){
			int c=s[i]-'a';
			if(date[I][c]==-1) date[I][c]=ID++;
			I=date[I][c];
			u[I]++;
		}
		v[I]++;
	}
	int Find(string s){
		int S=s.size(),I=0,res=-1;
		for(int i=0;i<S;i++){
			I=date[I][s[i]-'a'];
			res+=v[I];
		}
		return res;
	}
	vvi solve(string s){
		vvi a(26,vi(26));
		int S=s.size(),I=0;
		for(int i=0;i<S;i++){
			int c=s[i]-'a';
			for(int j=0;j<26;j++) if(j!=c&&date[I][j]!=-1) a[j][c]+=u[date[I][j]];
			I=date[I][c];
		}
		return a;
	}
};

int n,q;
vs a,t;

int main(){
	cin>>n;
	a=vs(n);
	vi b(n);
	vvi c(26);
	Trie trie;
	for(int i=0;i<n;i++){
		cin>>a[i];
		trie.Update(a[i]);
	}
	for(int i=0;i<n;i++) b[i]=trie.Find(a[i]);
	cin>>q;
	t=vs(q);
	vp d(q);
	vi res(q);
	for(int i=0;i<q;i++){
		int k;
		cin>>k>>t[i];
		d[i]={k-1,i};
	}
	sort(d.begin(),d.end());
	for(int i=0;i<q;i++){
		int k=d[i].first,I=d[i].second;
		string s=t[I];
		if(!i||k!=d[i-1].first) c=trie.solve(a[k]);
		res[I]=b[k];
		for(int j=0;j<26;j++) for(int l=0;l<j;l++) res[I]+=c[s[l]-'a'][s[j]-'a'];
	}
	for(int i=0;i<q;i++) cout<<res[i]+1<<endl;
}
### Prompt

Please provide a Cpp coded solution to the problem described below:

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 <iostream>
#include <fstream>
#include <cassert>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#include <time.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,string> pip;
typedef vector<pip> vip;
const int inf=2*1e9+1;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

class Trie{
	private:
	const int MAX=400005;
	int ID=1;
	vvi date;
	vi u,v;
	public:
	Trie(){
		date=vvi(MAX,vi(26,-1));
		u=v=vi(MAX);
	}
	void Update(string s){
		int S=s.size(),I=0;
		for(int i=0;i<S;i++){
			int c=s[i]-'a';
			if(date[I][c]==-1) date[I][c]=ID++;
			I=date[I][c];
			u[I]++;
		}
		v[I]++;
	}
	int Find(string s){
		int S=s.size(),I=0,res=-1;
		for(int i=0;i<S;i++){
			I=date[I][s[i]-'a'];
			res+=v[I];
		}
		return res;
	}
	vvi solve(string s){
		vvi a(26,vi(26));
		int S=s.size(),I=0;
		for(int i=0;i<S;i++){
			int c=s[i]-'a';
			for(int j=0;j<26;j++) if(j!=c&&date[I][j]!=-1) a[j][c]+=u[date[I][j]];
			I=date[I][c];
		}
		return a;
	}
};

int n,q;
vs a,t;

int main(){
	cin>>n;
	a=vs(n);
	vi b(n);
	vvi c(26);
	Trie trie;
	for(int i=0;i<n;i++){
		cin>>a[i];
		trie.Update(a[i]);
	}
	for(int i=0;i<n;i++) b[i]=trie.Find(a[i]);
	cin>>q;
	t=vs(q);
	vp d(q);
	vi res(q);
	for(int i=0;i<q;i++){
		int k;
		cin>>k>>t[i];
		d[i]={k-1,i};
	}
	sort(d.begin(),d.end());
	for(int i=0;i<q;i++){
		int k=d[i].first,I=d[i].second;
		string s=t[I];
		if(!i||k!=d[i-1].first) c=trie.solve(a[k]);
		res[I]=b[k];
		for(int j=0;j<26;j++) for(int l=0;l<j;l++) res[I]+=c[s[l]-'a'][s[j]-'a'];
	}
	for(int i=0;i<q;i++) cout<<res[i]+1<<endl;
}
```