T = gets.to_i
one = [p].size
two = [p, p].size
ten = [p,p,p,p,p,p,p,p,p,p].size
zc = (?z.ord - ?J.ord).chr
onec = (?z.ord - ?I.ord).chr
sevenc = (?z.ord - ?C.ord).chr
M = (onec + zc + zc + zc + zc + zc + zc + zc + zc + sevenc).to_i
l = [two, one]
a = $<.map &:to_i
(two..a.max).each{|i|
  l[i] = l[i-one] + l[i-two]
  l[i] -= M if l[i] >= M
}
a.each{|n|
  p l[n]
}