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