Hard lövhələr#3185
Super Board Games Inc. böyük bir stolüstü oyunlar istehsalçısıdır. Şirkətin əməkdaşları yeni bir oyun düşünüblər və bu oyunun çox populyar olacağı ehtimal edilir. Bu oyun üçün kvadrat hüceyrələrdən ibarət bir lövhə tələb olunur. Sol və aşağı kənarlar düz olmalı, hüceyrə sütunlarının hündürlüyü soldan sağa artmamalıdır. Əlavə olaraq, lövhənin hamısını 2×1 domino daşları ilə döşəmək mümkün olmalıdır. O, da müəyyən olunub ki, oyun ən maraqlı şəkildə n hüceyrəlik lövhədə oynanır. Şirkətin İdarə Heyəti qərara alıb ki, fərqli n-hüceyrəlik lövhələrdən maksimum sayda versiyanı buraxsın. Şirkətə müxtəlif lövhə variasiyalarının sayını tapmaqda kömək edin.
Şəkil 1: 8 hüceyrədən ibarət iki lövhə nümunəsi: biri düzgün (solda), digəri domino daşları ilə döşənə bilmir (sağda).
Birinci sətirdə bir tam ədəd T (1 \leq T \leq 100) — testlərin sayı verilir. Sonrakı T sətirin hər birində bir tam ədəd n (1 \leq n \leq 100) verilir.
Hər bir n üçün mümkün olan oyun versiyalarının sayını çap edin.
Nümunə 1