Easy lövhələr#3184
Super Board Games Inc. stolüstü oyunlar istehsal edən böyük bir şirkətdir. Onlar çox populyar olacağı gözlənilən yeni bir oyun icad ediblər. Bu oyun üçün lövhə kvadrat hüceyrələrə bölünmüş olmalıdır. Lövhənin sol və aşağı kənarları düz (səviyyəli) olmalı, sütunların hündürlüyü isə soldan sağa azalmamalıdır. Bundan əlavə, lövhəni tam şəkildə ölçüsü 2 \times 1 olan domino daşları ilə döşəmək mümkün olmalıdır.
Şirkətin idarə heyəti müəyyən edib ki, oyun ən maraqlı şəkildə, hüceyrədən ibarət lövhədə oynanılır. Buna görə də, fərqli -hüceyrəli lövhələrin hamısı üçün mümkün qədər çox sayda oyun versiyası buraxmaq qərarına gəliblər. Şirkətin buraxa biləcəyi fərqli lövhə variantlarının sayını hesablayın.
Şəkil 1: hüceyrədən ibarət iki lövhənin nümunəsi: domino daşları ilə döşənə bilən düzgün (solda), və döşənə bilməyən düzgün olmayan bir lövhə (sağda).
Birinci sətrdə (1 \leq T \leq 20) — testlərin sayı verilir. Növbəti sətrin hər birində bir tam ədəd (1 \leq n \leq 20) verilir.
Hər bir üçün oyunun mümkün olan variantlarının sayını çap edin.
Nümunə 1