Zoran 和 Tomislav 没有什么要紧的事做，所以他们整天都在做各种活动。今天，他们在后花园里建了一个高度为 $N$ 的金字塔，并在上面写上了他们最喜欢的单词。他们逐行循环书写该单词，且每行改变书写方向，如图所示。

高度为 6 且写有单词 “JANJETINA” 的金字塔

Tomislav 现在选择了金字塔的 $K$ 行，记为 $a_i$，并为每行选择了一个字母 $c_i$。然后他向 Zoran 提出了 $K$ 个刁钻的问题：“字母 $c_i$ 在第 $a_i$ 行中出现了多少次？”

你是 Zoran 的顾问。请编写一个程序，对于给定的金字塔高度和他们最喜欢的单词，回答 Tomislav 的问题。

输入格式

输入的第一行包含一个整数 $N$ ($1 \le N \le 10^{18}$)。

输入的第二行包含一个仅由大写英文字母组成的单词。单词的长度不超过 $10^6$。

输入的第三行包含一个整数 $K$ ($1 \le K \le 50\,000$)，表示 Tomislav 选择的行数。

接下来的 $K$ 行，每行包含一个数对 $a_i, c_i$ ($1 \le a_i \le N$，$c_i$ 为大写英文字母)，表示 Tomislav 的提问。

输出格式

输出 $K$ 行。输出的第 $i$ 行必须包含一个整数，即字母 $c_i$ 在第 $a_i$ 行中出现的次数。

数据范围

• 在占总分 50% 的测试数据中，$N$ 不超过 $1\,000$。
• 在占总分 70% 的测试数据中，字符串的长度不超过 $10^5$。

样例

输入格式 1

6
JANJETINA
5
1 J
1 A
6 N
6 I
5 E

输出格式 1

1
0
2
1
1

输入格式 2

5
A
5
1 A
2 A
3 A
4 A
5 B

输出格式 2

1
2
3
4
0

输入格式 3

3
AB
3
2 A
2 B
3 B

输出格式 3

1
1
2

说明

第一个样例的说明：见题目描述中的金字塔。