Lát gạch domino

Một nền nhà hình chữ nhật gồm \(2\) hàng và \(N\) cột ô vuông đơn vị cần được lát kín bằng các viên gạch domino kích thước \(1 \times 2\) (được phép xoay thành \(2 \times 1\)). Các viên gạch không được chồng lên nhau, không được nhô ra ngoài nền và không được để trống bất kỳ ô nào.

Với mỗi giá trị \(N\) cho trước, hãy đếm xem có bao nhiêu cách lát nền nhà. Hai cách lát là khác nhau nếu có ít nhất một viên gạch nằm ở vị trí khác nhau. Kết quả có thể rất lớn, hãy in ra giá trị chính xác (không lấy dư).

Input

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng bộ dữ liệu.
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(N\).

Output

Với mỗi bộ dữ liệu in ra một dòng là số cách lát nền tương ứng.

Constraints

• \(1 \le T \le 100\)
• \(1 \le N \le 200\)

Sample Input

3
3
5
6

Sample Output

3
8
13

Explanation

Với \(N = 3\) có \(3\) cách: xếp ba viên gạch đứng cạnh nhau; hoặc một viên đứng ở đầu trái rồi hai viên nằm ngang chồng lên nhau; hoặc hai viên nằm ngang rồi một viên đứng ở đầu phải.