Mil və kilometrlər#3188
Əgər siz tez-tez səyahət edirsinizsə, aşağıdakı problemlə rastlaşmış ola bilərsiniz: müxtəlif ölkələr fərqli ölçü sistemlərindən istifadə edir. Xüsusən də, məsafələr üçün iki əsas ölçü sistemi mövcuddur: metrik və imperiya (imperial) sistemi. Metrik sistemdə kilometr istifadə olunur, imperiya sistemində isə mil. Bilinir ki, bir mil təxminən kilometrdir. Maraqlı təsadüfdür ki, bu dəyər qızıl nisbətə də ( ətrafında) çox yaxındır. Bu əsasa əsaslanaraq, millərlə verilmiş məsafəni kilometrə çevirmək üçün maraqlı bir üsul mövcuddur.
Fibonacci ardıcıllığını nəzərdən keçirək: F_1 = F_2 = 1, F_n = F_{n-1} + F_{n-2}, n > 2 üçün. İki ardıcıl Fibonacci ədədlərinin nisbəti F_{n+1}/F_n sonsuzluğa yaxınlaşdıqca qızıl nisbətə yaxınlaşır. Deməli, millərin sayını ən böyük mümkün Fibonacci ədədlərindən istifadə edərək onların cəminə ayıra bilərsiniz. Sonra hər bir ədədi növbəti Fibonacci ədədinə dəyişib bu yeni ədədlərin cəmini tapırsınız. Bu yolla, kilometrin təxmini dəyərini əldə edirsiniz.
Məsələn, 40 \to 34 + 5 + 1 \to 55 + 8 + 2 \to 65. Deməli, mil təxminən kilometrdir (dəqiq dəyər kilometrdir). Bu üsulu reallaşdıran proqram yazın.
Girişin ilk sətrində (1 \leq t \leq 10000) — testlərin sayı verilir. Sonrakı sətirdə isə hər bir test təsviri verilir. Hər bir test bir tam ədədindən (1 \leq m \leq 10^{15}) — millərin sayından ibarətdir.
Hər bir test üçün, tapşırıqda təsvir edilən üsulla hesablanmış kilometrin təxmini sayını çap edin.
Nümunə 1