#include <fstream>
using namespace std;
ifstream f ( "x.in" );
#define LE  1006000
ofstream g ( "x.out" );
int n, m, l, A[LE], B[LE], x, y, i, Q;
#include <string>
string a, b;

int  okay ( int stanga, int dreapta )
{
    l = 1;

    while ( stanga >= 1 && dreapta <= n && l <= m )
    {
        if ( A[stanga] != B[l] )
            break;

        if ( A[dreapta] != B[l] )
            break;

        ++l;
        --stanga,++dreapta;
    }

    return l - 1;
}
int main()
{
    f >> n >> m >> Q;

    f >> a >> b;

    for ( i = 0; i < n; ++i )
        A[i+1] = a[i];

    for ( i = 0; i < m; ++i )
        B[i+1] = b[i];

    for ( i = 1; i <= Q; ++i )
    {
        f >> x >> y;

        g << okay ( x - 1, y + 1 ) << '\n';
    }




    f.close();
    g.close();
    return 0;
}