#include <bits/stdc++.h>
using namespace std ;

typedef long long LL ;
typedef pair < int , int > pii ;

#define clr( a , x ) memset ( a , x , sizeof a )

const int MAXN = 400005 ;

struct Node {
	char s[27] ;
	int idx ;
} ;

vector < Node > G[MAXN] ;

int nxt[MAXN][26] ;
int letter[MAXN] ;
int pre[MAXN] ;
int siz[MAXN] ;
int is[MAXN] ;
int word[MAXN] ;
int cur = 0 ;
int n , q ;
char s[MAXN] ;
int sum[26][26] ;
int to[26] ;
int ans[MAXN] ;

int newnode () {
	clr ( nxt[cur] , 0 ) ;
	siz[cur] = 0 ;
	is[cur] = 0 ;
	return cur ++ ;
}

int insert ( char s[] , int idx ) {
	int now = 0 ;
	for ( int i = 0 ; s[i] ; ++ i ) {
		int x = s[i] - 'a' ;
		if ( nxt[now][x] == 0 ) nxt[now][x] = newnode () ;
		pre[nxt[now][x]] = now ;
		now = nxt[now][x] ;
		letter[now] = x ;
		siz[now] ++ ;
	}
	is[now] ++ ;
	return now ;
}

void get ( int u ) {
	while ( u ) {
		for ( int i = 0 ; i < 26 ; ++ i ) if ( i != letter[u] ) {
			sum[i][letter[u]] += siz[nxt[pre[u]][i]] ;
		}
		sum[letter[u]][letter[u]] += is[pre[u]] ;
		u = pre[u] ;
	}
}

void solve () {
	cur = 0 ;
	newnode () ;
	clr ( sum , 0 ) ;
	for ( int i = 1 ; i <= n ; ++ i ) {
		scanf ( "%s" , s ) ;
		G[i].clear () ;
		word[i] = insert ( s , i ) ;
	}
	scanf ( "%d" , &q ) ;
	for ( int i = 0 ; i < q ; ++ i ) {
		Node tmp ;
		int u ;
		scanf ( "%d%s" , &u , tmp.s ) ;
		tmp.idx = i ;
		G[u].push_back ( tmp ) ;
	}
	for ( int i = 1 ; i <= n ; ++ i ) {
		clr ( sum , 0 ) ;
		get ( word[i] ) ;
		for ( int j = 0 ; j < G[i].size () ; ++ j ) {
			int tmp = 0 ;
			for ( int k = 0 ; k < 26 ; ++ k ) {
				to[k] = G[i][j].s[k] - 'a' ;
			}
			for ( int k = 0 ; k < 26 ; ++ k ) {
				for ( int l = k ; l < 26 ; ++ l ) {
					tmp += sum[to[k]][to[l]] ;
				}
			}
			ans[G[i][j].idx] = tmp ;
		}
	}
	for ( int i = 0 ; i < q ; ++ i ) {
		printf ( "%d\n" , ans[i] + 1 ) ;
	}
}

int main () {
	while ( ~scanf ( "%d" , &n ) ) solve () ;
	return 0 ;
}
### Prompt

Your challenge is to write 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 <bits/stdc++.h>
using namespace std ;

typedef long long LL ;
typedef pair < int , int > pii ;

#define clr( a , x ) memset ( a , x , sizeof a )

const int MAXN = 400005 ;

struct Node {
	char s[27] ;
	int idx ;
} ;

vector < Node > G[MAXN] ;

int nxt[MAXN][26] ;
int letter[MAXN] ;
int pre[MAXN] ;
int siz[MAXN] ;
int is[MAXN] ;
int word[MAXN] ;
int cur = 0 ;
int n , q ;
char s[MAXN] ;
int sum[26][26] ;
int to[26] ;
int ans[MAXN] ;

int newnode () {
	clr ( nxt[cur] , 0 ) ;
	siz[cur] = 0 ;
	is[cur] = 0 ;
	return cur ++ ;
}

int insert ( char s[] , int idx ) {
	int now = 0 ;
	for ( int i = 0 ; s[i] ; ++ i ) {
		int x = s[i] - 'a' ;
		if ( nxt[now][x] == 0 ) nxt[now][x] = newnode () ;
		pre[nxt[now][x]] = now ;
		now = nxt[now][x] ;
		letter[now] = x ;
		siz[now] ++ ;
	}
	is[now] ++ ;
	return now ;
}

void get ( int u ) {
	while ( u ) {
		for ( int i = 0 ; i < 26 ; ++ i ) if ( i != letter[u] ) {
			sum[i][letter[u]] += siz[nxt[pre[u]][i]] ;
		}
		sum[letter[u]][letter[u]] += is[pre[u]] ;
		u = pre[u] ;
	}
}

void solve () {
	cur = 0 ;
	newnode () ;
	clr ( sum , 0 ) ;
	for ( int i = 1 ; i <= n ; ++ i ) {
		scanf ( "%s" , s ) ;
		G[i].clear () ;
		word[i] = insert ( s , i ) ;
	}
	scanf ( "%d" , &q ) ;
	for ( int i = 0 ; i < q ; ++ i ) {
		Node tmp ;
		int u ;
		scanf ( "%d%s" , &u , tmp.s ) ;
		tmp.idx = i ;
		G[u].push_back ( tmp ) ;
	}
	for ( int i = 1 ; i <= n ; ++ i ) {
		clr ( sum , 0 ) ;
		get ( word[i] ) ;
		for ( int j = 0 ; j < G[i].size () ; ++ j ) {
			int tmp = 0 ;
			for ( int k = 0 ; k < 26 ; ++ k ) {
				to[k] = G[i][j].s[k] - 'a' ;
			}
			for ( int k = 0 ; k < 26 ; ++ k ) {
				for ( int l = k ; l < 26 ; ++ l ) {
					tmp += sum[to[k]][to[l]] ;
				}
			}
			ans[G[i][j].idx] = tmp ;
		}
	}
	for ( int i = 0 ; i < q ; ++ i ) {
		printf ( "%d\n" , ans[i] + 1 ) ;
	}
}

int main () {
	while ( ~scanf ( "%d" , &n ) ) solve () ;
	return 0 ;
}
```