끼룽의 블로그

# swea 3143 '가장 빠른 문자열 타이핑'

T = int(input())

for t in range(1, T+1):
    A, B = input().strip().split()

    jump_dict = {}
    for i in range(1, len(B)):
        if B[-1 - i] in jump_dict:
            continue
        jump_dict[B[-1 - i]] = i

    cnt = 0
    i = len(B) - 1
    k = 0

    while i < len(A):
        if k == len(B):
            jump = len(B)
            cnt += 1
            i += jump
            k = 0
            continue

        if A[i - k] == B[-1 - k]:
            k += 1
        else:
            jump = jump_dict.get(A[i], len(B))
            i += jump
            k = 0

    result = len(A) - cnt * (len(B) - 1)

    print('#{} {}'.format(t, result))