Розглянемо послідовність x_i, задану наступними співвідношеннями:
x_0 = a + b, x_1 = a – b,
x_i = (a·x_{i }_{- 2} + b·x_{i }_{- 1}) mod m, i > 1
Для заданого натурального n знайти довжину найбільшої зростаючої підпослідовності x_0, x_1, x_2, …, x_n.
Кожен тест складається з одного рядка, який містить чотири натуральних числа a, b, m, n (a ≥ b, 1 ≤ a, b, m, n ≤ 10^6). Кількість тестових випадків у одному тесті не перевищує 20.
Для кожного тесту в окремому рядку вивести довжину найбільшої зростаючої підпослідовності.