Fibonacci-ийн тоог нь дараах томъёогоор олдог

Дарааллын i-р гишүүн нь дараах томъёоны дагуу хувирдаг

• \(i<=2\) үед 1
• \(i>2\) үед F(i)=F(i-1)+F(i-2)

Танд a, b гэсэн бүхэл тоонууд өгөгдөнө. Таны далагавар бол [a,b] гэсэн завсарт орших F(x) тоо хэд байгааг тоолж олох явдал юм.

Оролт:

Оролтын файлын эхний мөрөнд асуулгын тоо болох q тоо өгөгдөнө.

дараагийн q ш мөрөнд мөр тус бүрд a, b гэсэн хос бүхэл тоонууд хоосон зайгаар тусгаарлан өгөгдөнө.

Гаралт:

Гаралтын файлд асуулгуудын хариу болох a,b завсар дахь F(x) -үүдийн тоог q ш мөр тус бүрд хэвлэнэ

Хязгаарлалтууд:

• \(q<=10^5\)
• \(2 ≤ a_i, b_i ≤ 10^{35}, i \in [1..q]\)

Дэд бодлого

Жишээ:

Оролт-1

2
1 10
8 100

Гаралт-1

5
6

Тайлбар

[1,10]-> {1,2,3,5,8} гэсэн 5 ш тоо байна

[8,100] -> {8,13,21,34,55,89} гэсэн 6 ш тоо байна.