Omy and Ish were learning the pattern printing. In order to learn they give themselves a task. In this task they are given a string and they have to form a pyramid with the pattern as follows:
RowNumber are one based indexed.
- 
If (RowNumber % 3 == 0) then string is written in left to right while in other cases it is written in right to left order.
- 
if the string end it will be started again and end of the pyramid need not to be the end of string.
For eg: string is “$CODING$” and height of pyramid is “$5$”
C
D O
I N G
I D O C
D O C G N

Omi will be asked $Q$ queries and he has to tell the frequency of a character  C in that particular row $R$ of pyramid.

-----Input:-----
- First line will contain $N$, height of pyramid.
- Next line contain a string consists only of Uppercase English Alphabets, length not exceed $10^6$
- Third line contain a single integer $Q$, the number of queries to be asked.
- Each query contain two space separated integers, $R$ and $C$, where $R$ is the row number and $C$ is the character.

-----Output:-----
- For each query, output in a single line the frequency of the alphabet in the given row.

-----Constraints:-----
- $1$ $\leq$ $N$ $\leq$ $10$^$18$
- $1$ $\leq$ $Q$ $\leq$ $50000$
- $1 \leq R \leq N$
- $A \leq C \leq Z$

-----Sample Input:-----
5
CODING
2
1 C
2 D

-----Sample Output:-----
1
1

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import sys\r\n\r\nn = int(sys.stdin.readline().strip())\r\ns = sys.stdin.readline().strip()\r\n\r\nalph = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"\r\n\r\narr = [0]*26\r\npref = []\r\n\r\nfor i in range(len(s)):\r\n\tfor j in range(26):\r\n\t\tif alph[j] == s[i]:\r\n\t\t\tarr[j] += 1\r\n\t\t\tbreak\r\n\tpref += [arr[:]]\r\n\r\n# for x in pref:\r\n# \tprint(x)\r\n\r\nq = int(sys.stdin.readline().strip())\r\n\r\nfor _ in range(q):\r\n\tr, c = sys.stdin.readline().strip().split()\r\n\r\n\tfor i in range(26):\r\n\t\tif alph[i] == c:\r\n\t\t\tind = i\r\n\t\t\tbreak\r\n\r\n\tr = int(r)\r\n\r\n\tprev = ((r-1)**2 + r-1)//2\r\n\r\n\tdone = prev%len(s)\r\n\r\n\tans = 0\r\n\trem = (len(s) - done)%len(s)\r\n\r\n\tif r <= rem:\r\n\t\tprint(pref[done+r-1][ind] - pref[done-1][ind])\r\n\t\tcontinue\r\n\r\n\tif rem != 0:\r\n\t\tans += pref[-1][ind] - pref[done-1][ind]\r\n\t\tr -= rem\r\n\r\n\tans += pref[-1][ind] * (r//len(s))\r\n\tr %= len(s)\r\n\r\n\t# print("AA", ans, r)\r\n\r\n\tif r != 0:\r\n\t\tans += pref[r-1][ind]\r\n\r\n\tprint(ans)\r\n\r\n\r\n\t# print(rem, done, prev)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14025