12669_1

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <ctype.h>
#include <cstdlib>

using namespace std;
string T, P;
int b[100010], n, m, numofoccurrence, maxdiff;

string flipcase(string s)
{
    string ret = "";
    for (int i = 0; i < strlen(s.c_str()); i++)
    {
        ret += isupper(s[i]) ? tolower(s[i]) : islower(s[i]) ? toupper(s[i]) : s[i];
    }
    return ret;
}

string convtolower(string s)
{
    string ret = "";
    for (int i = 0; i < strlen(s.c_str()); i++)
    {
        ret += isupper(s[i]) ? tolower(s[i]) : s[i];

    }
    return ret;
}

int calculateDiff(string s1, string s2)
{
    int numofdiff = 0;
    for (int i = 0; i < strlen(s1.c_str()); i++)
    {
        if (s1[i] != s2[i]) numofdiff += 1;
    }
    return numofdiff;
}

void kmpPreprocess()
{
    int i = 0, j = -1; b[0] = -1;
    while (i < m)
    {
        while (j >= 0 && (P[i] != P[j])) j = b[j];
        i++; j++;
        b[i] = j;
    }
}

void kmpSearch(string cursub, string cmain)
{
    int i = 0, j = 0;
    while (i < n)
    {
        while (j >= 0 && (T[i] != P[j])) j = b[j];
        i++; j++;
        if (j == m)
        {

            string occurstr = "";
            numofoccurrence += 1;
            int stindex = (i - j);
            int edindex = (stindex + strlen(cursub.c_str()));
            for (int x = stindex; x < edindex; x++)
            {
                occurstr += cmain[x];

            }


            int curdiff = calculateDiff(occurstr, cursub);
            if (curdiff > maxdiff) maxdiff = curdiff;

            j = b[j];
        }
    }
}



int main()
{
    string origsub, origmain, sublower, mainlower;
    int N, sublen, i, L, R, j;




    while (cin>>N>>origsub)
    {




        cin>>origmain;
        for (i = 0; i < N; i++)
        {
            cin>>L>>R;
            string curmain = "";
            for (j = (L - 1); j < R; j++)
            {
                curmain += origmain[j];
            }

            sublower = convtolower(origsub);
            mainlower = convtolower(curmain);
            T = mainlower; n = strlen(T.c_str());
            P = sublower; m = strlen(P.c_str());
            kmpPreprocess();
            numofoccurrence = 0;
            maxdiff = 0;
            kmpSearch(origsub, curmain);
            if (numofoccurrence == 0)
            {
                printf("-1\n");
            }
            else
            {
                printf("%d\n", maxdiff);
            }

            string temp = "";
            for (j = 0; j < (L - 1); j++)
            {
                temp += origmain[j];
            }


            temp += flipcase(curmain);


            for (j = R; j < strlen(origmain.c_str()); j++)
            {
                temp += origmain[j];
            }
            origmain = temp;

        }



    }


    return 0;
}