module Main where

-- https://www.hackerrank.com/challenges/aorb/problem

import Control.Monad (replicateM_)
import Data.Bits (Bits (shiftL, shiftR, (.&.)))
import Data.Char (toUpper)
import Data.Maybe (listToMaybe)
import Numeric (readHex, showHex)

-- utility functions

intToBinList :: Integer -> [Integer]
intToBinList 0 = [0]
intToBinList n = reverse (go n)
  where
    go 0 = []
    go x =
        let bit = x .&. 1
         in bit : go (x `shiftR` 1)

-- specifics

parseInputs :: (Integer, String, String, String) -> Maybe (Integer, Integer, Integer, Integer)
parseInputs (k, a, b, c) = do
    a' <- fst <$> listToMaybe (readHex a)
    b' <- fst <$> listToMaybe (readHex b)
    c' <- fst <$> listToMaybe (readHex c)
    return (k, a', b', c')

normalizeInputs :: (Integer, Integer, Integer, Integer) -> (Integer, [(Integer, Integer, Integer)])
normalizeInputs (k, a, b, c) =
    -- base arrays
    let al = intToBinList a
        bl = intToBinList b
        cl = intToBinList c
        -- normalize arrays, prepending zeros
        width = maximum [length al, length bl, length cl]
        a' = replicate (width - length al) 0 ++ al
        b' = replicate (width - length bl) 0 ++ bl
        c' = replicate (width - length cl) 0 ++ cl
     in -- return normalized inputs
        (k, zip3 a' b' c')

forcedPass :: (Integer, [(Integer, Integer, Integer)]) -> Maybe (Integer, [(Integer, Integer, Integer)])
forcedPass (k, zs) = do
    let (k', zs') = go k zs []
    if k' < 0
        then Nothing
        else Just (k', zs')
  where
    go k [] acc = (k, reverse acc)
    go k ((a, b, 0) : zs) acc = go (k - a - b) zs ((0, 0, 0) : acc)
    go k ((0, 0, 1) : zs) acc = go (k - 1) zs ((0, 1, 1) : acc)
    go k ((a, b, c) : zs) acc = go k zs ((a, b, c) : acc) -- leave it for now

discretionaryPass :: (Integer, [(Integer, Integer, Integer)]) -> (Integer, [(Integer, Integer, Integer)])
discretionaryPass (k, zs) = go k zs []
  where
    go k [] acc = (k, reverse acc) -- stopping condition
    go 0 (z : zs) acc = go 0 zs (z : acc) -- run it out
    go k ((0, 0, 0) : zs) acc = go k zs ((0, 0, 0) : acc) -- leave it
    go k ((0, 1, 1) : zs) acc = go k zs ((0, 1, 1) : acc) -- leave it
    go k ((1, 0, 1) : zs) acc =
        if k >= 2
            then go (k - 2) zs ((0, 1, 1) : acc)
            else go k zs ((1, 0, 1) : acc) -- leave it
    go k ((1, 1, 1) : zs) acc = go (k - 1) zs ((0, 1, 1) : acc)
    go k ((a, b, c) : zs) acc = error $ "discretionaryPass: unexpected values encountered: " ++ show (a, b, c)

reassemble :: (Integer, [(Integer, Integer, Integer)]) -> (Integer, Integer, Integer, Integer)
reassemble (k, zs) =
    let (as, bs, cs) = unzip3 zs
        a = foldl (\acc x -> acc `shiftL` 1 + x) 0 as
        b = foldl (\acc x -> acc `shiftL` 1 + x) 0 bs
        c = foldl (\acc x -> acc `shiftL` 1 + x) 0 cs
     in (k, a, b, c)

display :: (Integer, Integer, Integer, Integer) -> IO ()
display (k, a, b, c) = do
    putStrLn $ map toUpper $ showHex a ""
    putStrLn $ map toUpper $ showHex b ""

solve :: (Integer, String, String, String) -> Maybe (Integer, Integer, Integer, Integer)
solve inputs = do
    parsed <- parseInputs inputs
    let normalized = normalizeInputs parsed
    forced <- forcedPass normalized
    let discretionary = discretionaryPass forced
    return $ reassemble discretionary

main :: IO ()
main = do
    cases <- readLn :: IO Int
    replicateM_ cases $ do
        k <- readLn :: IO Integer
        aHex <- getLine
        bHex <- getLine
        cHex <- getLine
        let inputs = (k, aHex, bHex, cHex)
        case solve inputs of
            Just sol -> display sol
            Nothing -> putStrLn "-1"