import Control.Monad (when)
import System.IO (hFlush, stdout)

-- Simplify a number within modulo n
simplify :: Int -> Int -> Int
simplify x n = (x `mod` n + n) `mod` n

-- Query function
query :: Int -> Int -> Int -> IO Int
query n u v = do
    putStrLn $ "? " ++ show (simplify u n + 1) ++ " " ++ show (simplify v n + 1)
    hFlush stdout
    readLn

-- Answer function
answer :: Int -> Int -> Int -> IO ()
answer n u v = do
    putStrLn $ "! " ++ show (simplify u n + 1) ++ " " ++ show (simplify v n + 1)
    hFlush stdout
    x <- readLn
    when (x == -1) $ error "Terminated"

-- Binary search helper
binarySearch :: Int -> Int -> (Int -> IO Bool) -> IO Int
binarySearch l r check
    | l < r = do
        let mid = (l + r + 1) `div` 2
        isValid <- check mid
        if isValid
            then binarySearch mid r check
            else binarySearch l (mid - 1) check
    | otherwise = return l

-- Main logic
solve :: IO ()
solve = do
    t <- readLn
    let loop 0 = return ()
        loop t = do
            n <- readLn
            let half = n `div` 2
            let quarter = n `div` 4
            let recur x y = do
                    d <- query n x y
                    if d /= half
                        then return (x, y, d)
                        else recur (x + quarter) (y + quarter)
            (x0, y0, d0) <- recur 0 (n `div` 2)
            let x = simplify x0 n
            let y = simplify y0 n

            let findOffset dir = do
                    let check mid = do
                            let y' = if dir == -1 then y - mid else y + mid
                            query n x y' >>= \d -> return (d == d0 - mid)
                    binarySearch 1 (d0 - 1) check

            y' <- ifM (query n x (y - 1) >>= \d -> return (d == d0 - 1))
                      (findOffset (-1) >>= \l -> return $ simplify (y - l) n)
                      (findOffset 1 >>= \l -> return $ simplify (y + l) n)
            let d = query n x y'
            let finalX = ifM (query n (x + 1) y' >>= \d -> return (d == d0 - 1))
                             (return $ simplify (x + d - 1) n)
                             (return $ simplify (x - (d - 1)) n)
            answer n finalX y'
            loop (t - 1)
    loop t

-- Helper function for ifM
ifM :: Monad m => m Bool -> m a -> m a -> m a
ifM cond trueBranch falseBranch = do
    c <- cond
    if c then trueBranch else falseBranch

-- Entry point
main :: IO ()
main = solve

<no location info>: warning:
    -XGeneralizedNewtypeDeriving is not allowed in Safe Haskell; ignoring -XGeneralizedNewtypeDeriving
[1 of 2] Compiling Main             ( answer.hs, answer.o )

answer.hs:63:54: error:
    • Couldn't match expected type ‘Int’ with actual type ‘IO Int’
    • In the second argument of ‘(+)’, namely ‘d’
      In the first argument of ‘(-)’, namely ‘x + d’
      In the first argument of ‘simplify’, namely ‘(x + d - 1)’
   |
63 |                              (return $ simplify (x + d - 1) n)
   |                                                      ^

answer.hs:64:55: error:
    • Couldn't match expected type ‘Int’ with actual type ‘IO Int’
    • In the first argument of ‘(-)’, namely ‘d’
      In the second argument of ‘(-)’, namely ‘(d - 1)’
      In the first argument of ‘simplify’, namely ‘(x - (d - 1))’
   |
64 |                              (return $ simplify (x - (d - 1)) n)
   |                                                       ^

answer.hs:65:22: error:
    • Couldn't match expected type ‘Int’ with actual type ‘IO Int’
    • In the second argument of ‘answer’, namely ‘finalX’
      In a stmt of a 'do' block: answer n finalX y'
      In the expression:
        do n <- readLn
           let half = n `div` 2
           let quarter = n `div` 4
           let recur x y = ...
           ....
   |
65 |             answer n finalX y'
   |                      ^^^^^^