[SWEA] 글자 수

T = int(input())
for TC in range(T):
    str1 = input()
    str2 = input()
    N = len(str1)
    M = len(str2)
    max_num = 0
    counts = [0]*N

    for i in range(M):
        for j in range(N):
            if str1[j] == str2[i]:
                counts[j] += 1
    for i in range(N):
        if counts[i] > max_num:
            max_num = counts[i]
    print('#{} {}'.format(TC+1, max_num))