Програмчлалын олимпиадын бодлогын архив

Фибоначийн тоон дарааллын гишүүн бүр нь өмнөх 2 гишүүдийнхээ нийлбэртэй тэнцүү байдаг билээ.  Эхний 2 гишүүн нь 1 ба 2 байх эхний 10 гишүүнийг бичвэл 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,... болно. Дурын натурал тоог Фибоначийн дэс дараалсан биш хэд хэдэн ялгаатай  гишүүдийн нийлбэрт нэгэн утгатай бичиж болно.

Жишээ нь. 100 = 3 + 8 + 89, 11=3+8.

n тооны хувьд Фибоначийн тооны хэдэн гишүүний нийлбэр болж байгааг s(n) –ээр тэмдэглэе.    s(5) = 1, s(11) = 2, s(100) = 3 гэх мэт.

Даалгавар.  N тоо хүртэлх s(n)-ийн нийлбэрийг ол.  

Input

Эхний мөрөнд нь мөрөнд  оролтын өгөгдлийн тоо T, дараагийн Т ширхэг мөрөнд N-ийн утгыг илэрхийлэх нэг нэг натурал тоо байрлана.  T (1<=T<=10), N(0<N<10¹⁷)

Output

Даалгаврын нөхцөлийг хангах T ширхэг тоо (2⁶⁴-1 тооноос хэтрэхгүй) нэг нэг мөрөнд байрлана. 

Example

Input:
2
10
14

Output:
15
23