Zoran and Tomislav don't really have anything important to do, so they spend their days doing various activities. Today, they built a pyramid of the height in the back garden and wrote their favorite word on it, repeating it from line to line and changing direction, as shown in the picture.

```
J
N A
J E T
J A N I
A N J E T
N A J A N I
```

*Pyramid of the height 6 marked with the word JANJETINA*

Tomislav has now chosen lines of the pyramid, marked with , and has chosen a letter for each line. Then he asked Zoran tricky questions: "How many times does the letter appear in the row ?"

You are Zoran's counselor. Write a programme that will, for the given pyramid height and their favorite word, answer Tomislav's questions.

#### Input

The first line of input contains the integer .

The second line of input contains a word that consists of only uppercase letters of the English alphabet. The word's length will not exceed .

The third line of input contains the integer , the number of lines Tomislav has chosen.

Each of the following lines contains the pair , (, uppercase letter of the English alphabet) which represent Tomislav's questions.

#### Output

Output lines. The line of output must contain a single integer – the number of appearances of letter in the row .

#### Scoring

In test cases worth 50% of total points, will not exceed . In test cases worth 70% of total points, length of the string will not exceed .

#### Sample Input 1

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

#### Sample Output 1

```
1
0
2
1
1
```

#### Explanation for Sample 1

See the pyramid in the task statement.

#### Sample Input 2

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

#### Sample Output 2

```
1
2
3
4
0
```

#### Sample Input 3

```
3
AB
3
2 A
2 B
3 B
```

#### Sample Output 3

```
1
1
2
```

## Comments

why i get mle the judge is joking me he input big numbers and i get mle

The judge isn't joking you :)

Likely you used dp to solve the problem and you created a big array! But you can use another creative idea to reduce memory.

You can create 26

`vector`

and for any letter like you save some numbers like such that in sorted form. Then create a function to find number of letter in range and use binary search.sorry for my poor English!

I don't know what I did wrong. 5th batch case and onward I have WA. Can someone give me a hint on what I did wrong?

Mybe for big numbers (numbers like so that )! I got WA for that too but I fixed it!

dont know how to solve this

all test cases after the 5th one fail... :(