def longest_common_prefix_suffix(a, b):
    n = len(a)
    m = len(b)
    lcp = [[0 for _ in range(m+1)] for _ in range(n+1)]
    for i in range(n+1):
        for j in range(m+1):
            if i == 0 or j == 0:
                lcp[i][j] = 0
            elif a[i-1] == b[m-j]:
                lcp[i][j] = lcp[i-1][j-1] + 1
            else:
                lcp[i][j] = 0
    return max(max(row) for row in lcp)

T = int(input())
for t in range(1, T+1):
    A, B, Q = input().split()
    Q = int(Q)
    A_prefixes = set()
    B_suffixes = set()
    for i in range(Q):
        P, S = map(int, input().split())
        A_prefixes.add(A[:P])
        B_suffixes.add(B[-S:])
    ans = [longest_common_prefix_suffix(a, b) for a in A_prefixes for b in B_suffixes]
    ans.sort(reverse=True)
    print(f"Case #{t}: {' '.join(str(x) for x in ans[:Q])}")