Növbəti şəkildə verilmiş x_i ardıcıllığına baxaq:
x_0 = a + b, x_1 = a – b,
x_i = (a·x_{i }_{- 2} + b·x_{i }_{- 1}) mod m, i > 1
Verilmiş n natural ədədi üçün x_0, x_1, x_2, …, x_n ən böyük artan alt ardıcıllığının uzunluğunu tapın.
Hər bir test dörd natural a, b, m, n (a ≥ b,1 ≤ a, b, m, n ≤ 10^6) ədədlərini ehtiva edən tək sətirdən ibarətdir. Bir testdəki test hallarının sayı 20-ni aşmır.
Hər bir test üçün tək sətirdə ən böyük artan alt ardıcıllığın uzunluğunu verin.