Kkunglish

Kkung practiced hard to type English faster, and now he can type a lot of English in almost no time.

Because he only worked on speed, the English he types has no spaces and no punctuation, and the letter cases are all over the place. Nobody can read a sentence like that, and people call it Kkunglish. For example, the sentence programming is great turns into PrOgRAMmINgiSgrEAt once Kkung types it.

To find out how complicated the Kkunglish he made is, Kkung came up with the following procedure. First he picks one word $T$. Then, inside a substring of the Kkunglish sentence, he finds every position where $T$ occurs when case is ignored, and for each position he counts how many letters differ from $T$ in case. The largest of those numbers is the complexity of that substring. A position where $T$ occurs has to lie entirely inside the substring.

Say $T$ is GR and Kkung picks the substring PrOgRAM of PrOgRAMmINgiSgrEAt. Then $T$ occurs at gR only and one letter differs in case, so the complexity is 1. In that same substring PrOgRAM, if $T$ becomes r, then $T$ occurs at r and at R, the two candidate values are 0 and 1, and the complexity is 1.

Kkung is not a nice person, so he added one more rule to annoy you further. After one complexity is computed, the case of the substring he just picked is flipped, and then the next complexity can be computed. For example, if the complexity of PrOgRAM in PrOgRAMmINgiSgrEAt was computed, the next complexity is computed on pRoGrammINgiSgrEAt, where the first seven letters are flipped. If the complexity of the substring ammINgi of pRoGrammINgiSgrEAt was computed next, the one after that is computed on pRoGrAMMinGISgrEAt. The case is flipped the same way even when the complexity is -1.

Even Kkung, who made the rule, gets confused. Write the program that computes the complexity.

You are given the $T$ that Kkung picked, one Kkunglish sentence, and the substrings Kkung will pick, in that order. Compute the complexity for each of them.

The first line contains an integer $N$ ($1 \le N \le 10^5$) and a word $T$, separated by a space. $N$ is the number of times a substring is picked, and the length of $T$ is at most 5.

The second line contains the Kkunglish sentence $P$, which has no spaces. The length of $P$ is at most $10^5$.

Each of the next $N$ lines contains two integers $L$, $R$ ($1 \le L \le R \le |P|$). This means the substring from the $L$-th letter to the $R$-th letter of $P$ is picked and its complexity is computed. The leftmost letter of the sentence is the 1st letter, and the rightmost letter is the $|P|$-th letter.

$T$ and $P$ consist of uppercase and lowercase English letters only.

Print $N$ lines, one integer per line. On the $i$-th line, print the complexity of the $i$-th picked substring. If $T$ never occurs inside that substring when case is ignored, print -1.

Let $T$ be gR and let the first Kkunglish sentence be PrOgRAMmINgiSgrEAt. Picking the ranges (1, 7), (4, 18), (6, 14) in that order goes as follows.

The substring from the 1st to the 7th letter is PrOgRAM, and 0 is the only candidate value. Once the computation is done, the case of that range is flipped and the sentence turns into pRoGrammINgiSgrEAt.

The substring from the 4th to the 18th letter is GrammINgiSgrEAt, and the candidate values are 2 and 1. Once the computation is done, the sentence turns into pRogRAMMinGIsGReaT.

The substring from the 6th to the 14th letter is AMMinGIsG, and there is no candidate value at all.