Thuật toán Ứng dụng - K59PM - ĐH Thủy Lợi

        Ở công viên thành phố có 1 bức tường, trên bức tường người ta gắn 1 bức phù điêu tái hiện sự kiện lịch sử của thành phố. Ở dưới chân bức tường người ta dự định ốp gạch trang trí trên 1 khoảng hình chữ nhật có kích thước 2xN có 2 loại gạch 1x2 và 2x2.

          Hãy xác định số cách ốp.

Input

          - Dòng đầu chứa số bộ test T.

          - T dòng sau mỗi dòng chứa 1 số nguyên dương N (N<=20).

Output

          - T dòng, mỗi dòng chứa 1 số là kết quả của bài toán.

Example

Input:
3
1
2
12
Output:
1
3
2731