# Arup Guha
# Solution to CIS 3362 Homework #3 Problem #4
# 9/6/2024

# Returns a 5 x 5 grid of the key (storing j only)
def getGrid(key):

    # Initially store as a 1D grid.
    onedgrid = []
    
    # Stores used letters.
    used = []
    for i in range(26):
        used.append(False)

    for i in range(len(key)):

        # Skip over these.
        if used[ord(key[i])-ord('a')]:
            continue

        # This goes next. I am always storing j...
        if key[i] != 'i':
            onedgrid.append(key[i])
        else:
            onedgrid.append('j')

        # Mark it as used and handle i, j as a special case.
        used[ord(key[i])-ord('a')] = True
        if key[i] == 'i' or key[i] == 'j':
            used[ord('i')-ord('a')] = True
            used[ord('j')-ord('a')] = True

    # Copy all unused letters except for i into the grid.
    for i in range(26):
        if not used[i] and i != ord('i')-ord('a'):
            onedgrid.append(chr(ord('a')+i))

    # Make it two d.
    res = []
    for i in range(5):
        res.append([])
        for j in range(5):
            res[i].append(onedgrid[5*i+j])

    # Ta da!
    return res

# Returns a map version of gridkey.
def convertKey(gridkey):

    # Store map here.
    mymap = {}

    # Go through key.
    for i in range(len(gridkey)):
        for j in range(len(gridkey[i])):
            val = gridkey[i][j]
            mymap[val] = (i, j)

            # Special for i.
            if val == 'j':
                mymap['i'] = (i, j)

    # Ta da!
    return mymap

# Encrypts the pair digraph using the key stored in mymap.
def ePair(digraph, gridkey, mymap):

    # Get locations.
    loc1 = mymap[digraph[0]]
    loc2 = mymap[digraph[1]]

    # Same row.
    if loc1[0] == loc2[0]:
        c1 = (loc1[1]+1)%5
        c2 = (loc2[1]+1)%5
        return gridkey[loc1[0]][c1] + gridkey[loc1[0]][c2]

    # Same col.
    elif loc1[1] == loc2[1]:
        r1 = (loc1[0]+1)%5
        r2 = (loc2[0]+1)%5
        return gridkey[r1][loc1[1]] + gridkey[r2][loc1[1]]

    # Box
    else:
        return gridkey[loc1[0]][loc2[1]] + gridkey[loc2[0]][loc1[1]]
    
    
# Encrypts the message msg using the key stored in gridkey and mymap.
def encrypt(msg, gridkey, mymap):

    res = ""

    # Index into msg.
    i = 0

    # Go through msg.
    while i < len(msg):

        digraph = msg[i:min(i+2,len(msg))]

        # Padding case.
        if len(digraph) == 1 or digraph[0] == digraph[1]:

            # Get rid of the second letter if we need to.
            if len(digraph) == 2:
                digraph = digraph[0:1]

            # Add padding.
            if digraph[0] != 'x':
                digraph = digraph + 'x'
            else:
                digraph = digraph + 'q'
            i += 1

        # Digraph is good so we just advance.
        else:
            i += 2

        # Add to end.
        res = res + ePair(digraph, gridkey, mymap)

    return res
def main():

    nC = int(input())

    # Process messages.
    for loop in range(nC):

        # Get key and convert it to a map where we map the letter to
        # its position in the grid. We store both versions for ease.
        key = input().strip()
        gridkey = getGrid(key)
        mymap = convertKey(gridkey)

        # Get message.
        msg = input().strip()

        # Encrypt it and print.
        print(encrypt(msg, gridkey, mymap))

# Run it.
main()