The largest increasing subsequence#1988
Consider the sequence x_i given by the following relations:
x_0 = a + b, x_1 = a - b,
x_i = (a \cdot x_{i-2} + b \cdot x_{i-1}) \bmod m, i > 1
For a given positive integer , find the length of the longest increasing subsequence among x_0, x_1, x_2, \ldots, x_n.
Each test consists of one line containing the four natural numbers , , , (a \geq b, 1 \leq a, b, m, n \leq 10^6). The number of test cases in a single test does not exceed .
For each test, output on a separate line the length of the longest increasing subsequence.
Example 1