Cherry has a string S$S$ consisting of lowercase English letters. Using this string, he formed a pyramid of infinite length with certain rules:
- N$N$-th row of pyramid contains N$N$ characters.
- Each row of pyramid begins with the first character of the string.
- The subsequent characters of the row are appended to the string in cyclic fashion, until the size of string for that Row is reached (See example pyramid for better understanding).
He has another string T$T$ of smaller (or equal) size.
You are asked Q$Q$ queries. Each query is provided with a row number N$N$. The answer to the query is number of occurrences of string T$T$ in that particular row of pyramid. No of occurrences of String T$T$ in a string V$V$ would mean that you'd need to find number of substrings Vi,Vi+1...Vj$V_i, V_{i+1} ... V_j$ which are equal to String T$T$, where i≤j$i \leq j$.
For eg: If the string is code, then the pyramid will be of the form:
c
co
cod
code
codec
codeco
codecod
codecode
codecodec
codecodeco
...

-----Input:-----
- The first line contains string S$S$ — consisting of lowercase English letters.
- The second line contains string T$T$ — consisting of lowercase English letters.
- Next line contains an integer Q$Q$ — the number of queries.
- Then follow Q$Q$ lines with queries descriptions. Each of them contains a single integer N$N$ denoting the row number of pyramid.

-----Output:-----
- Print Q$Q$ lines. The i$i$-th of them should contain a integer denoting occurrences of string T$T$ in that particular row.

-----Constraints-----
- 1≤|S|≤105$1 \leq |S| \leq 10^5$
- 1≤|T|≤|S|$1 \leq |T| \leq |S|$
- 1≤Q≤105$1 \leq Q \leq 10^5$
- 1≤N≤109$1 \leq N \leq 10^9$

-----Sample Input:-----
codechef
chefcode
3
4
12
1455

-----Sample Output:-----
0
1
181

-----Explanation:-----
Pyramid will be formed as explained in the statement.
Query 1: Row number 4 of the pyramid is code. The number of occurrences of chefcode in code is 0.
Query 2: Row number 12 of the pyramid is codechefcode. The number of occurrences of chefcode in codechefcode is 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 = 'def search(arr, lenl, val):\r\n    s = 0\r\n    l = lenl - 1\r\n\r\n    total = 0\r\n\r\n    while (s <= l):\r\n        m = int((s + l) / 2)\r\n\r\n        if (arr[m] <= val):\r\n            total = m + 1\r\n            s = m + 1\r\n\r\n        else:\r\n            l = m - 1\r\n\r\n    return total\r\n\r\n\r\ndef kmpsearch(string, lps):\r\n    lis = []\r\n    lens = len(string)\r\n    lensh = lens // 2\r\n\r\n    l = 0\r\n    i = 0\r\n    while i < lens:\r\n        if string[i] == pat[l]:\r\n            l += 1\r\n            i += 1\r\n        elif l > 0:\r\n            l = lps[l - 1]\r\n        else:\r\n            i += 1\r\n\r\n        if l == lenp:\r\n            if i - l < lensh:\r\n                lis.append(i - l)\r\n\r\n            l = lps[l - 1]\r\n\r\n    return lis\r\n\r\n\r\ndef kmp(pat, lenp):\r\n\r\n    lps = [0]*(lenp)\r\n    l = 0\r\n    i = 1\r\n\r\n    while i < lenp:\r\n        if pat[i] == pat[l]:\r\n            l += 1\r\n            lps[i] = l\r\n            i += 1\r\n        elif l > 0:\r\n            l = lps[l-1]\r\n        else:\r\n            lps[i] = 0\r\n            i += 1\r\n\r\n    return lps\r\n\r\n\r\n\r\nkeyword = input()\r\npat = input()\r\nq = int(input())\r\n\r\nlenk = len(keyword)\r\nlenp = len(pat)\r\n\r\nk = keyword * 2\r\nlis = kmpsearch(k, kmp(pat, lenp))\r\nlenl = len(lis)\r\n\r\nfor _ in range(q):\r\n    n = int(input())\r\n    count = 0\r\n\r\n    q = n // lenk\r\n    r = n % lenk\r\n\r\n    count += search(lis, lenl, r - lenp)\r\n\r\n    if q >= 1:\r\n        count += search(lis, lenl, lenk + r - lenp)\r\n\r\n    if q >= 2:\r\n        count += (q - 1)*lenl\r\n\r\n    print(count)\r\n    \r\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13651