Наибольшая возрастающая подпоследовательность

Рассмотрим последовательность 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.

Выходные данные

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

Примеры