main = interact $ unlines . map (show . train2) . tail . lines

train2 ts = nub' ts . sum . map combs . partitions $ ts
nub' xs n = n - (length xs - 2) * 2
partitions xs = map (flip splitAt xs) [1..(length xs)-1]
palin xs = xs == reverse xs
combs (xs1,xs2) = div (same * palin1 * palin2) palin12
 where
  same = if xs1==xs2 then 1 else 2
  palin1 = if palin xs1 then 1 else 2
  palin2 = if palin xs2 then 1 else 2
  palin12 = if xs1 == reverse xs2 then 3 else 1