# Arup Guha
# Decrypt El-Gamal for Question #4 CIS 3362
# 11/8/2025

import math

# Returns a list storing [x, y, gcd(a,b)] where ax + by = gcd(a,b).
def EEA(a,b):

    # End of algorithm, 1*a + 0*b = a
    if b == 0:
        return [1,0,a]

    # Recursive case.
    else:

        # Next quotient and remainder.
        q = a//b
        r = a%b

        # Algorithm runs on b, r.
        rec = EEA(b,r)

        # Here is how we put the solution back together!
        return [rec[1], rec[0]-q*rec[1], rec[2]]

# Returns the modular inverse of x mod n. 
# Returns 0 if there is no modular inverse.
def modInv(x,n):

    # Call the Extended Euclidean.
    arr = EEA(n, x)

    # Indicates that there is no solution.
    if arr[2] != 1:
        return 0

    # Do the wrap around, if necessary.
    if arr[1] < 0:
        arr[1] += n

    # This is the modular inverse.
    return arr[1]

# Converts number val storing a block of length characters to those lowercase letters.
def convert(val,length):

    s = ""
    for i in range(length):

        # This is the last character left.
        c = chr(ord('a')+val%26)

        # prepend so it builds backwards.
        s = c + s

        # Peel off this letter.
        val = val//26

    return s


def main():
    # I added this it's the number of blocks in the input.
    n = int(input())

    # Hard-coded from previous step in write up.
    q = 1234567890133
    xA = 794703949047

    # Decrypt each block.
    for i in range(n):

        # Get block.
        toks = input().split()
        c1 = int(toks[0])
        c2 = int(toks[1])

        # Get K from Bob.
        K = pow(c1, xA, q)

        # Extract it's inverse mod q.
        Kinv = modInv(K, q)

        # Get message by multiplying C2 by Kinv.
        numM = (Kinv*c2)%q

        # Get all on one line. I'll space out later.
        print(convert(numM, 8), end="")

main()