Trong một chuyến dạo chơi quanh công viên, bé Bie thấy các bác công nhân đang xây một đường phân cách với kích thước 1xN (1 ≤ N ≤ 90) giữa bãi cỏ công viên và đường đi trong công viên. Các bác công nhân sử dụng hai loại gạch với kích thước 1x1 và 1x2. Với trí tò mò, bé Bie muốn tính được số cách sắp xếp các loại gạch sao cho được đường phân cách 1xN. Nhiệm vụ của bạn hãy giúp bé tìm được kết quả.

Dữ liệu nhập: 

• Dòng đầu tiên bao gồm số T (1 ≤ T ≤ 100), là số bộ test.
• T dòng tiếp theo, mỗi dòng chứa một số N tương ứng với mỗi bộ test.

Kết quả xuất: 

• T dòng, mỗi dòng in kết quả tương ứng với số nguyên dương N.

Ví dụ:

Nhập:
2
2
3

Xuất:
2
3