#include<iostream>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<numeric>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
using ulong = unsigned long;
using ll = long long;
const int M = 1e9 + 7;
#pragma unused(M)
 
struct Node{
	char chr;
	Node* par;
	bool used = false;
	map<char, pair<int, Node*>> dests;
	Node(){}
	Node(Node* n):par(n){}
	// Node* make(string& str, int idx){
	// 	chr = str[idx];
	// 	if(str.size() == idx + 1){ return this; }
	// 	char next = str[idx + 1];
	// 	if(dests.count(next)){
	// 		dests[next].first++;
	// 	}else{
	// 		Node* n = new Node(this);
	// 		dests[next] = {1, n};
	// 	}
	// 	return dests[next].second -> make(str, idx + 1);
	// }
	// int calc(vector<int>& ord){
	// 	return par -> _calc(ord, chr) + 1;
	// }
	// int _calc(vector<int>& ord, char from){
	// 	int ret = used;
	// 	for(auto& dest : dests){
	// 		if(ord[dest.first - 'a'] < ord[from - 'a']){
	// 			ret += dest.second.first;
	// 		}
	// 	}
	// 	if(par == nullptr){ return ret; }
	// 	return par -> _calc(ord, chr) + ret;
	// }
};
vector<Node> pool(400000);
int pidx;
Node* make(Node* n, string& str, int idx){
	while(1){
		// n -> chr = str[idx];
		if(str.size() == idx){ return n; }
		char next = str[idx];
		if(n -> dests.count(next)){
			n -> dests[next].first++;
		}else{
			pool[pidx].par = n;
			n -> dests[next] = {1, &pool[pidx++]};
		}
		idx++;
		n = n -> dests[next].second;
		n -> chr = str[idx - 1];
	}
}

void opt(){
	for(Node& n : pool){
		if(n.used == false && n.dests.size() == 1){
			n.dests.begin() -> second.second -> par = n.par;
			n.dests.begin() -> second.second -> chr = n.chr;
			n.par -> dests[n.chr].second = n.dests.begin() -> second.second;
		}
	}
}

int calc(Node* n, vector<int>& ord){
	int ret = 1;
	char from;
	while(1){
		from = n -> chr;
		n = n -> par;
		if(!n){ return ret; }
		ret += n -> used;
		for(auto& dest : n -> dests){
			if(ord[dest.first - 'a'] < ord[from - 'a']){
				ret += dest.second.first;
			}
		}
	}
}
 
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, q;
	cin >> n;
	Node root(nullptr);
	vector<Node*> nodes(n);
	for(int i=0;i<n;i++){
		string s;
		cin >> s;
		// s = 'a' + s;
		// nodes[i] = root.make(s, 0);
		nodes[i] = make(&root, s, 0);
		nodes[i] -> used = true;
	}
 
	opt();
 
	cin >> q;
	vector<int> ord(26);
	for(int i=0;i<q;i++){
		int k;
		string p;
		cin >> k >> p;
		for(int i=0;i<26;i++){
			ord[p[i] - 'a'] = i;
		}
		k--;
		// cout << nodes[k] -> calc(ord) << endl;
		cout << calc(nodes[k], ord) << endl;
	}
	return 0;
}

### Prompt

Please formulate a CPP solution 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<iostream>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<numeric>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
using ulong = unsigned long;
using ll = long long;
const int M = 1e9 + 7;
#pragma unused(M)
 
struct Node{
	char chr;
	Node* par;
	bool used = false;
	map<char, pair<int, Node*>> dests;
	Node(){}
	Node(Node* n):par(n){}
	// Node* make(string& str, int idx){
	// 	chr = str[idx];
	// 	if(str.size() == idx + 1){ return this; }
	// 	char next = str[idx + 1];
	// 	if(dests.count(next)){
	// 		dests[next].first++;
	// 	}else{
	// 		Node* n = new Node(this);
	// 		dests[next] = {1, n};
	// 	}
	// 	return dests[next].second -> make(str, idx + 1);
	// }
	// int calc(vector<int>& ord){
	// 	return par -> _calc(ord, chr) + 1;
	// }
	// int _calc(vector<int>& ord, char from){
	// 	int ret = used;
	// 	for(auto& dest : dests){
	// 		if(ord[dest.first - 'a'] < ord[from - 'a']){
	// 			ret += dest.second.first;
	// 		}
	// 	}
	// 	if(par == nullptr){ return ret; }
	// 	return par -> _calc(ord, chr) + ret;
	// }
};
vector<Node> pool(400000);
int pidx;
Node* make(Node* n, string& str, int idx){
	while(1){
		// n -> chr = str[idx];
		if(str.size() == idx){ return n; }
		char next = str[idx];
		if(n -> dests.count(next)){
			n -> dests[next].first++;
		}else{
			pool[pidx].par = n;
			n -> dests[next] = {1, &pool[pidx++]};
		}
		idx++;
		n = n -> dests[next].second;
		n -> chr = str[idx - 1];
	}
}

void opt(){
	for(Node& n : pool){
		if(n.used == false && n.dests.size() == 1){
			n.dests.begin() -> second.second -> par = n.par;
			n.dests.begin() -> second.second -> chr = n.chr;
			n.par -> dests[n.chr].second = n.dests.begin() -> second.second;
		}
	}
}

int calc(Node* n, vector<int>& ord){
	int ret = 1;
	char from;
	while(1){
		from = n -> chr;
		n = n -> par;
		if(!n){ return ret; }
		ret += n -> used;
		for(auto& dest : n -> dests){
			if(ord[dest.first - 'a'] < ord[from - 'a']){
				ret += dest.second.first;
			}
		}
	}
}
 
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, q;
	cin >> n;
	Node root(nullptr);
	vector<Node*> nodes(n);
	for(int i=0;i<n;i++){
		string s;
		cin >> s;
		// s = 'a' + s;
		// nodes[i] = root.make(s, 0);
		nodes[i] = make(&root, s, 0);
		nodes[i] -> used = true;
	}
 
	opt();
 
	cin >> q;
	vector<int> ord(26);
	for(int i=0;i<q;i++){
		int k;
		string p;
		cin >> k >> p;
		for(int i=0;i<26;i++){
			ord[p[i] - 'a'] = i;
		}
		k--;
		// cout << nodes[k] -> calc(ord) << endl;
		cout << calc(nodes[k], ord) << endl;
	}
	return 0;
}

```