An và Bình đang tìm hiểu về các dãy số trong toán học. Một trong những dãy số đầu tiên và nổi tiếng nhất mà các bạn được học là dãy Fibonacci.

Dãy Fibonacci được định nghĩa như sau:

• Số đầu tiên và thứ hai của dãy là 0 và 1.
• Kể từ số thứ ba trở đi, mỗi số là tổng của hai số liền trước nó.

Dãy số bắt đầu như sau: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Thầy giáo muốn kiểm tra xem hai bạn đã hiểu bài chưa bằng cách yêu cầu tìm số Fibonacci thứ ~n~. Bạn hãy viết một chương trình với một hàm để tìm số Fibonacci thứ ~n~ giúp hai bạn nhé.

Định dạng đầu vào

Dòng đầu tiên chứa một số nguyên ~T~ (~1 \le T \le 100~), là số lượng các số cần tìm.

~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~n~ (~0 \le n \le 45~).

Định dạng đầu ra

Đối với mỗi số nguyên ~n~, in ra số Fibonacci thứ ~n~ trên một dòng riêng biệt.

Sample Input

3
0
5
8

Sample Output

0
5
21