from typing import List, Tuple

def get_longest_common_prefix(a: str, b: str, p: int, s: int) -> int:
    """
    Returns the length of the longest substring from the A-prefix that matches the B-suffix.
    """
    a_prefix = a[:p]
    b_suffix = b[-s:]
    longest_common_prefix = 0
    for i in range(p):
        if a_prefix[i:] not in b_suffix:
            break
        longest_common_prefix = i + 1
    return longest_common_prefix

def process_test_case(a: str, b: str, q: int, tests: List[Tuple[int, int]]) -> List[int]:
    """
    Processes a single test case and returns a list of results for the queries in the test case.
    """
    results = []
    for pi, si in tests:
        longest_common_prefix = get_longest_common_prefix(a, b, pi, si)
        results.append(longest_common_prefix)
    return results

if __name__ == "__main__":
    t = int(input())
    for case in range(1, t + 1):
        a, b, q = input().split()
        q = int(q)
        tests = []
        for i in range(q):
            pi, si = map(int, input().split())
            tests.append((pi, si))
        results = process_test_case(a, b, q, tests)
        print(f"Case #{case}: {' '.join(str(r) for r in results)}")