Q = gets.to_i
Q.times do
  N = gets.to_i
  if N.even?
    puts 998244349
  else
    puts 4
  end
end