B - Bantove cisla

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Jedneho dna sedel Banto len tak sam vo svojom domceku. "Mal by som sa pripravovat na test", pomyslel si. A mal pravdu. Uz zajtra ho cakal velky test z postupnosti a radov. No nie a nie sa prinutit otvorit zosit. Uz ho aj zacinalo hryzt svedomie, ked tu dostal spasonosnu myslienku. Aby nemusel otvarat knizku, rozhodol sa, ze si sam vymysli nejaku rekurentnu postupnost a skusi urcit jej vlastnosti. Zobral papier a len tak nan napisal:

B(x)=B(x-1)+B(x-2)-B(x-3)

"Hmm, to vyzera celkom dobre", pomyslel si, "Este by sa ziadalo doplnit zaciatocne hodnoty."

B(1)=1
B(2)=3
B(3)=5

Teda 4. Bantove cislo B(4)=B(3)+B(2)-B(1)=5+3-1

Takto vznikla Bantova postupnost cisel. Cely naradosteny sa dal do skumania vlastnosti. Rad by nejako vypocital, kolko Bantovych cisel lezi v nejakom urcenom intervale.

Uloha

Zistite kolko Bantovych cisel sa nachadza v zadanom uzavretom intervale.

Vstup

Prvy riadok vstupu obsahuje cislo N, 1 ≤ N ≤ 1000, pocet intervalov. Dalsich N riadkov obsahuje po dve cisla A,B, 1 ≤ A ≤ B ≤ 1000000000 (miliarda), hranice intervalu. Cisla A,B patria do intervalu.

Vystup

Vystup ma obsahovat N riadkov. Kazdy riadok ma obsahovat jedno cele cislo, pocet Bantovych cisel v zadanom intervale.

Priklad

Vstup:

Vystup:

V intervale <1,5> sa nachadzaju cisla {1,3,5}, v intervale <1,4> sa nachadzaju cisla {1,3}, v intervale <4,4> nie je ziadne cislo a v intervale <5,5> je jedine cislo 5

Problem by Samuel BWPOW Kupka.

DS2004