{-# LANGUAGE FlexibleInstances, UndecidableInstances, DuplicateRecordFields #-}

module Main where

import Control.Monad
import Data.List
import Data.List.Split
import Data.Map (Map)
import qualified Data.Map as Map
import System.Environment
import System.IO


-- Complete the function below.

maximumPermutation w s =
    let l = length w
        j = fromIntegral l :: Integer
        h = hash j w 0
        g = hash j (take l s) 0
        k = otherHash (take l s) 0
        m = findPerms s (drop l s) j h g k Map.empty
        r = getMaxFromMap m
    in fromKey j "" $ headOr r (-1)

fromKey :: Integer -> String -> Integer -> String
fromKey _ _ (-1) = "-1"
fromKey 0 s _ = s
fromKey j s x = fromKey (j-1) (c:s) (div x 26)
    where c = toEnum $ fromIntegral ((mod x 26) + 97)

hash :: Integer -> [Integer] -> Integer -> Integer
hash _ [] h = h
hash l (x:xs) h = hash l xs (h + (l ^ x))

updtHash :: Integer -> Integer -> Integer -> Integer -> Integer
updtHash l h x y = h + (l ^ y) - (l ^ x)

otherHash :: [Integer] -> Integer -> Integer
otherHash [] h = h
otherHash (x:xs) h = otherHash xs ((26 * h) + x)

updtOthrHash :: Integer -> Integer -> Integer -> Integer -> Integer
updtOthrHash l h x y = (26 * (h - ((26 ^ (l-1)) * x))) + y

findPerms :: [Integer] -> [Integer] -> Integer -> Integer -> Integer -> Integer -> Map Integer Integer -> Map Integer Integer
findPerms [] _ _ _ _ _ m = m
findPerms _ [] _ _ _ _ m = m
findPerms (x:xs) (y:ys) l h g k m
    | h == g    = findPerms xs ys l h (updtHash l g x y) (updtOthrHash l k x y) (Map.insertWith (+) k 1 m)
    | otherwise = findPerms xs ys l h (updtHash l g x y) (updtOthrHash l k x y) m

headOr [] x = x
headOr (x:_) _ = x

getMaxFromMap m = go [] Nothing (Map.toDescList m)
  where
    go ks _        []           = ks
    go ks Nothing  ((k,v):rest) = go (k:ks) (Just v) rest
    go ks (Just u) ((k,v):rest)
        | v < u     = go ks     (Just u) rest
        | v > u     = go [k]    (Just v) rest
        | otherwise = go (k:ks) (Just v) rest


main :: IO()
main = do
    fileName <- getEnv "OUTPUT_PATH"
    out <- openFile fileName WriteMode

    t <- readLn :: IO Int

    forM_ [1..t] $ \tItr -> do
        w <- getLine

        s <- getLine

        let result = maximumPermutation (toIs w) (toIs s)

        hPutStrLn out result

    hFlush out
    hClose out

toIs :: [Char] -> [Integer]
toIs xs = map ( (subtract 97) . fromIntegral . fromEnum ) xs