def longest_prefix_suffix_match(A, B : str, P, S):
    """
    Retourne la longueur de la plus longue sous-chaîne de A[0:P] qui correspond au suffixe de B[0:S].
    """
    max_length = 0
    for i in range(P):
        # Trouver toutes les sous-chaînes de A[0:P] qui commencent à la position i.
        substrings = [A[i:j+1] for j in range(i, P)]
        # Vérifier si chaque sous-chaîne correspond au suffixe de B[0:S].
        for substring in substrings:
            if B[-S:].startswith(substring):
                max_length = max(max_length, len(substring))
    return max_length

# Lecture de l'entrée
T = int(input())
for i in range(T):
    A, B, Q = input().split()
    Q = int(Q)
    # Traitement des tests
    results = []
    for j in range(Q):
        P, S = map(int, input().split())
        results.append(longest_prefix_suffix_match(A, B, P, S))
    # Affichage des résultats
    print("Case #{}: {}".format(i+1, " ".join(str(r) for r in results)))