#include<iostream>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<algorithm>
#include<cstring>
#include<string>
#include<cassert>
#include<cmath>
#include<climits>
#include<iomanip>
#include<stack>
#include<unordered_map>
#include<bitset>
#include<limits>
#include<complex>
#include<array>
#include<numeric>
#include<functional>
#include<random>

using namespace std;
#define ll long long
#define ull unsigned long long
#define rrep(i,m,n) for(ll (i)=(ll)(m);(i)>=(ll)(n);(i)--)
#define rep(i,m,n) for(ll (i)=(ll)(m);i<(ll)(n);i++)
#define REP(i,n) rep(i,0,n)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define all(hoge) (hoge).begin(),(hoge).end()
typedef pair<ll, ll> P;
constexpr long double m_pi = 3.1415926535897932L;
constexpr ll MOD = 1000000007;
constexpr ll INF = 1LL << 61;
constexpr long double EPS = 1e-10;
template<typename T> using vector2 = vector<vector<T>>;
template<typename T> using vector3 = vector<vector2<T>>;
typedef vector<ll> Array;
typedef vector<Array> Matrix;

class AhoCorasick {
private:
	vector2<int> nxt;//現在のノードにchを追加した場合のノード　存在しなければsuffix linkを辿る
	vector<int> fail, end;//suffix link,そのノードに存在する文字列の数
	int root;
	int p;//ノードの数
	int maxn;//文字の合計サイズ
	vector<int> gen, num;
public:
	AhoCorasick(int maxn) 
		:maxn(maxn), nxt(maxn, vector<int>(26, -1)), fail(maxn), end(maxn, 0), p(1), root(0) ,gen(maxn,0),num(maxn,0){}

	inline void insert(const string& s) {
		int now = root;
		for (int i = 0; i < s.size(); i++) {
			if (nxt[now][s[i] - 'a'] == -1) nxt[now][s[i] - 'a'] = p++, gen[p-1] = gen[now] + 1;
			now = nxt[now][s[i] - 'a'];
		}
		end[now]++;
	}
	pair<int,int> dfs(int now) {
		pair<int, int> ret = { end[now],now };
		int cnt = 0;
		REP(i, 26) {
			if (nxt[now][i] == -1)continue;
			auto tmp = dfs(nxt[now][i]);
			nxt[now][i] = tmp.second;
			ret.first += tmp.first;
			cnt++;
		}
		num[now] = ret.first;
		if (end[now] == 0 && cnt == 1) {
			REP(i, 26)if (nxt[now][i] != -1) {
				ret.second = nxt[now][i];
			}
		}
		return ret;
	}
	inline int solve(string& s,string &t,int now) {
		ll g = gen[now];
		if (g == s.size())return 0;
		int ret = end[now];
		REP(i, 26) {
			if (s[g] == t[i]) {
				ret += solve(s, t, nxt[now][s[g] - 'a']);
				break;
			}
			if (nxt[now][t[i] - 'a'] == -1)continue;
			ret += num[nxt[now][t[i] - 'a']];
		}
		return ret;
	}
};

int main() {
	ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);

	ll n;
	cin >> n;
	AhoCorasick ac(404040);
	vector<string> s(n);
	for (auto& e : s)cin >> e, ac.insert(e);
	ac.dfs(0);
	ll q;
	cin >> q;
	while (q--) {
		ll k;
		string t;
		cin >> k >> t;
		k--;
		cout << ac.solve(s[k], t, 0) + 1 << "\n";
	}

	return 0;
}
### Prompt

Develop a solution in CPP 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<vector>
#include<set>
#include<queue>
#include<map>
#include<algorithm>
#include<cstring>
#include<string>
#include<cassert>
#include<cmath>
#include<climits>
#include<iomanip>
#include<stack>
#include<unordered_map>
#include<bitset>
#include<limits>
#include<complex>
#include<array>
#include<numeric>
#include<functional>
#include<random>

using namespace std;
#define ll long long
#define ull unsigned long long
#define rrep(i,m,n) for(ll (i)=(ll)(m);(i)>=(ll)(n);(i)--)
#define rep(i,m,n) for(ll (i)=(ll)(m);i<(ll)(n);i++)
#define REP(i,n) rep(i,0,n)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define all(hoge) (hoge).begin(),(hoge).end()
typedef pair<ll, ll> P;
constexpr long double m_pi = 3.1415926535897932L;
constexpr ll MOD = 1000000007;
constexpr ll INF = 1LL << 61;
constexpr long double EPS = 1e-10;
template<typename T> using vector2 = vector<vector<T>>;
template<typename T> using vector3 = vector<vector2<T>>;
typedef vector<ll> Array;
typedef vector<Array> Matrix;

class AhoCorasick {
private:
	vector2<int> nxt;//現在のノードにchを追加した場合のノード　存在しなければsuffix linkを辿る
	vector<int> fail, end;//suffix link,そのノードに存在する文字列の数
	int root;
	int p;//ノードの数
	int maxn;//文字の合計サイズ
	vector<int> gen, num;
public:
	AhoCorasick(int maxn) 
		:maxn(maxn), nxt(maxn, vector<int>(26, -1)), fail(maxn), end(maxn, 0), p(1), root(0) ,gen(maxn,0),num(maxn,0){}

	inline void insert(const string& s) {
		int now = root;
		for (int i = 0; i < s.size(); i++) {
			if (nxt[now][s[i] - 'a'] == -1) nxt[now][s[i] - 'a'] = p++, gen[p-1] = gen[now] + 1;
			now = nxt[now][s[i] - 'a'];
		}
		end[now]++;
	}
	pair<int,int> dfs(int now) {
		pair<int, int> ret = { end[now],now };
		int cnt = 0;
		REP(i, 26) {
			if (nxt[now][i] == -1)continue;
			auto tmp = dfs(nxt[now][i]);
			nxt[now][i] = tmp.second;
			ret.first += tmp.first;
			cnt++;
		}
		num[now] = ret.first;
		if (end[now] == 0 && cnt == 1) {
			REP(i, 26)if (nxt[now][i] != -1) {
				ret.second = nxt[now][i];
			}
		}
		return ret;
	}
	inline int solve(string& s,string &t,int now) {
		ll g = gen[now];
		if (g == s.size())return 0;
		int ret = end[now];
		REP(i, 26) {
			if (s[g] == t[i]) {
				ret += solve(s, t, nxt[now][s[g] - 'a']);
				break;
			}
			if (nxt[now][t[i] - 'a'] == -1)continue;
			ret += num[nxt[now][t[i] - 'a']];
		}
		return ret;
	}
};

int main() {
	ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);

	ll n;
	cin >> n;
	AhoCorasick ac(404040);
	vector<string> s(n);
	for (auto& e : s)cin >> e, ac.insert(e);
	ac.dfs(0);
	ll q;
	cin >> q;
	while (q--) {
		ll k;
		string t;
		cin >> k >> t;
		k--;
		cout << ac.solve(s[k], t, 0) + 1 << "\n";
	}

	return 0;
}
```