Dãy số tự nhiên ~F_0, F_1, F_2, \dots, F_n, \dots~ được gọi là dãy Fibonacci nếu thỏa mãn:

$$ F_0 = 0,\quad F_1 = 1,\quad F_n = F_{n-1} + F_{n-2}\ (n = 2, 3, 4, \dots) $$

Gọi ~S_n~ là tổng của ~n+1~ số đầu tiên trong dãy Fibonacci, tức là ~S_n = F_0 + F_1 + \dots + F_n~.

Cho ~m~ số nguyên ~n~, hãy tính giá trị ~S_n~ tương ứng với từng số ~n~ đó.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~m~ (~1 \le m \le 10^6~).
• Dòng tiếp theo chứa ~m~ số nguyên dương là các số ~n~ (~0 \le n \le 80~), hai số liên tiếp cách nhau ít nhất một khoảng trắng.

Kết quả

In ra ~m~ số, là giá trị ~S_n~ của các số ~n~ theo đúng thứ tự trong dữ liệu vào. Hai số liên tiếp cách nhau ít nhất một khoảng trắng.

Ví dụ

Ví dụ 1

TONGNF.INP

5
6 2 8 1 0

TONGNF.OUT

20 2 54 1 0

Ví dụ 2

TONGNF.INP

10
13 6 15 11 8 5 10 15 13 8

TONGNF.OUT

609 20 1596 232 54 12 143 1596 609 54

Giới hạn

• Subtask 1 (50% số điểm): ~1 \le m \le 10^5~; ~0 \le n \le 40~.
• Subtask 2 (50% số điểm): ~1 \le m \le 10^5~; ~0 \le n \le 80~.