t = int(input())

for case in range(1, t+1):
    A, B, Q = input().split()
    Q = int(Q)
    n, m = len(A), len(B)
    pre_sum = [[0 for _ in range(m+1)] for _ in range(n+1)]
    for i in range(n):
        for j in range(m):
            if A[i] == B[j]:
                pre_sum[i+1][j+1] = pre_sum[i][j] + 1
            else:
                pre_sum[i+1][j+1] = pre_sum[i][j+1]

    print("Case #{}:".format(case), end=" ")
    for i in range(Q):
        P, S = input().split()
        P, S = int(P), int(S)
        count = 0
        for j in range(P):
            if j+S-1 < m:
                count += pre_sum[j+1][j+S]
        print(count, end=" ")
    print()