{-# LANGUAGE FlexibleInstances #-}
module Main where

import Data.Char

import Control.Monad
import Control.Monad.Primitive
import Control.Monad.ST

import Control.Concurrent
import Control.Parallel.Strategies

import Data.Vector.Unboxed ((!))
import qualified Data.Vector.Unboxed as Vec
import qualified Data.Vector.Unboxed.Mutable as MVec

import GenerateCases



type NumDigits = Int
type DigitIndex = Int
type Digit = Int

class FastFixedWidthInteger a where
  numDigits :: a -> NumDigits
  digit :: DigitIndex -> a -> Digit
  addAt :: PrimMonad m => a -> DigitIndex -> Digit -> m a
  fromString :: String -> a
  toString :: a -> String



-- Slowest (omg)
instance FastFixedWidthInteger Integer where
  numDigits x | x < 10    = 1
              | otherwise = 1 + numDigits (x `div` 10)

  digit di x | di == 0   = fromInteger $ x `mod` 10
             | otherwise = digit (di-1) (x `div` 10)

  addAt x di d = return $ x + toInteger d * (10 ^ toInteger di)

  fromString = read
  toString   = show



-- Fast (mutable Vector)
instance FastFixedWidthInteger (Vec.Vector Digit) where
  numDigits    = Vec.length

  digit di x   = x ! di

  fromString   = Vec.fromList . map digitToInt . reverse

  toString     = map intToDigit . Vec.toList

  addAt x di d | newD <= 9 = do v <- Vec.unsafeThaw x
                                MVec.write v di newD
                                Vec.unsafeFreeze v
               | otherwise = do v <- Vec.unsafeThaw x
                                MVec.write v di mod'
                                v' <- Vec.unsafeFreeze v
                                addAt v' (di+1) div'
    where newD        = (x ! di) + d
          (div',mod') = newD `divMod` (10 :: Int)
-- TODO: if x is a sequences of nines, addAt is not going to work
--       because it cannot add a new digit at the end



digitPair :: FastFixedWidthInteger a =>
             NumDigits -> DigitIndex -> a -> (Digit, Digit)
digitPair nd di x = (digit di x, digit (nd-di-1) x)



type NumConsecutiveNines = Int

numConsecutiveNines :: FastFixedWidthInteger a =>
                       Digit -> NumConsecutiveNines -> DigitIndex ->
                       a -> Int
numConsecutiveNines d ncn di x
  | d /= 9    = ncn
  | otherwise = numConsecutiveNines dNext (ncn+1) diNext x
  where diNext = di+1
        dNext  = digit diNext x



palindromize' :: (PrimMonad m, FastFixedWidthInteger a) =>
                 (NumDigits,Int,Int) -> DigitIndex -> a -> m a
palindromize' cn@(nd,nddiv2,nddiv2sub1) di x
  | di == nddiv2    = return x
  | low < high      = palindromize' cn diNext =<< addAt x di diff
  | low == high     = palindromize' cn diNext x
  | ncn > 0         = palindromize' cn diBacktrack =<< xNextm
  | di < nddiv2sub1 = palindromize' cn diNext =<< xNextm
  | otherwise       = palindromize' cn di =<< xNextm
  where diNext      = di+1
        (low,high)  = digitPair nd di x
        ncn         = numConsecutiveNines low 0 diNext x
        diBacktrack = max 0 (di-ncn-1)
        diff        = high-low
        xNextm      = addAt x di $ 10+diff
        

palindromize :: (PrimMonad m, FastFixedWidthInteger a) => a -> m a
palindromize x = palindromize' (nd,nddiv2,nddiv2-1) 0 x
  where nd     = numDigits x
        nddiv2 = nd `div` 2

nextPalindrome :: (PrimMonad m, FastFixedWidthInteger a) => a -> m a
nextPalindrome x = palindromize =<< addAt x 0 1



main :: IO ()
main = do
  numCases <- getLine
  let n = read numCases :: Int
   in if n == 0
      then do numCasesToGenerate <- getLine
              let m = read numCasesToGenerate :: Int
               in do print m
                     generateCases m
      else do cap   <- getNumCapabilities
              cases <- replicateM n getLine
              let strategy = parBuffer cap rdeepseq
                  answers  = map (palindrome.fromString) cases `using` strategy
               in mapM_ (putStrLn.toString) answers
  where palindrome c = runST $ nextPalindrome c :: Vec.Vector Digit