Một người đang leo một chiếc cầu thang có ~x~ bậc. Anh ta có thể đi lên 1 bậc hoặc 2 bậc mỗi lần. Hỏi anh ta có bao nhiêu cách khác nhau để leo lên đến bậc cuối cùng?

Input: có q test

• Dòng 1: ghi số nguyên q (q<=10^6);
• Dòng 2: ghi n số nguyên dương x (x<=90), các số ghi cách nhau 1 dấu cách.

Output

• Ghi trên q dòng, mỗi dòng là kết quả tương ứng.

Sample input1

5
1 5 3 2 4

Sample output1

1
8
3
2
5