Найбільша зростаюча підпослідовність

Розглянемо послідовність 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.

Вихідні дані

Для кожного тесту в окремому рядку вивести довжину найбільшої зростаючої підпослідовності.

Приклади