Fibonaççi ədədləri

Bilindiyi kimi, Fibonaççi ardıcıllığı növbəti şəkildə təyin edilir.:

F(0) = 0, F(1) = 1, F(n) = F(n-1)+F(n-2) (bütün n > 1 üçün).

O Leonardo Pizanskiy adı ilə də tanınan İtalyan riyaziyyatçısı Leonardo Fibonaççinın şərəfinə adlandırılmışdır.

Verilmiş n və m qiymətlərinə görə F(n) və F(m)-nin ən böyük ortaq bölünənini hesablayın.

Giriş verilənləri

Hər bir sətir ayrı bir testdir və iki n və m (1 ≤ n, m ≤10^18) tam ədədlərini ehtiva edir. Testlərin sayı 1000 mini aşmır.

Çıxış verilənləri

Hər bir test üçün ayrı sətirdə ƏBOB(F(n),F(m)) qiymətini 10^8 modluna görə verin.

Nümunələr