Consider the sequence of \textbf{x_i}, given by the following relations: \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} For a given positive integer \textbf{n}, find the length of the longest increasing subsequence \textbf{x_0}, \textbf{x_1}, \textbf{x_2}, …, \textbf{x_n}. \InputFile Each test consists of one line containing the four natural numbers \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}). Number of test cases in a single test does not exceed \textbf{20}. \OutputFile For each test on a separate line to derive maximum length of increasing subsequences.