Pizano Dövrü#6390
1960-cı ildə IBM-dən Donald Wall, New York, White Plains-də, Fibonacci ədədlərinin çoxluğunun m modulu üzrə periodik olduğunu sübut etdi.
Gəlin ilk on Fibonacci ədədini və onların 11 ilə bölünməsindən qalan qalıqları nəzərdən keçirək:
Qalıqların ardıcıllığı təkrarlanır. Qoy k(m) - təkrarlanan altardıcıllığın uzunluğu olsun, onda k(11) = 10.
Wall bir neçə xüsusiyyəti sübut etdi, bunlardan bəziləri sizin üçün maraqlı ola bilər:
Əgər m > 2, onda k(m) cütdür.
Hər hansı cüt n > 2 üçün elə bir m mövcuddur ki, k(m) = n.
k(m) ≤ m^2 - 1
k(2^n) ≤ 3 * 2^{(n-1)}
k(5^n) = 4 * 5^n
k(2 * 5^n) = 6n
Əgər n > 2, onda k(10n) = 15 * 10^{(n-1)}
Müxtəlif modul m dəyərləri üçün təkrarlanan altardıcıllığın uzunluğunu k(m) hesablayan proqram yazın.
Birinci sətir testlərin sayı p (1 ≤ p ≤ 1000) ehtiva edir. Hər bir testin məlumatları bir sətirdə yerləşir və iki tam ədəd n və m ehtiva edir, burada n - testin nömrəsi, m (2 ≤ m ≤ 1000000) - modulun dəyəridir.
Hər bir test üçün ayrıca sətirdə testin nömrəsini n, boşluq və m üçün təkrarlanan altardıcıllığın uzunluğunu - k(m) dəyərini çıxarın.
Nümunə 1