Növbəti şəkildə verilmiş \textbf{x_i} ardıcıllığına baxaq: \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} Verilmiş \textbf{n} natural ədədi üçün \textbf{x_0}, \textbf{x_1}, \textbf{x_2}, …, \textbf{x_n} ən böyük artan alt ardıcıllığının uzunluğunu tapın. \InputFile Hər bir test dörd natural \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}) ədədlərini ehtiva edən tək sətirdən ibarətdir. Bir testdəki test hallarının sayı \textbf{20}-ni aşmır. \OutputFile Hər bir test üçün tək sətirdə ən böyük artan alt ardıcıllığın uzunluğunu verin.