Найбільша зростаюча підпослідовність#1988
Розглянемо послідовність x_i, задану такими співвідношеннями:
x_0 = a + b, x_1 = a - b,
x_i = (a \cdot x_{i-2} + b \cdot x_{i-1}) \bmod m, i > 1
Для заданого додатного цілого числа знайдіть довжину найдовшої зростаючої підпослідовності серед елементів x_0, x_1, x_2, \ldots, x_n.
Кожен тест складається з одного рядка, який містить чотири натуральні числа , , , (a \geq b, 1 \leq a, b, m, n \leq 10^6). Кількість тестів в одному файлі не перевищує .
Для кожного тесту в окремому рядку виведіть довжину найдовшої зростаючої підпослідовності.
Приклад 1