The largest increasing subsequence

Consider the sequence of x_i, given by the following relations:

x_0 = a + b, x_1 = a – b,

x_i = (a·x_{i }_{-2} + b·x_{i }_{- 1}) mod m, i > 1

For a given positive integer n, find the length of the longest increasing subsequence x_0, x_1, x_2, …, x_n.

Input

Each test consists of one line containing the four natural numbers a, b, m, n (a ≥ b, 1 ≤ a, b, m, n ≤ 10^6). Number of test cases in a single test does not exceed 20.

Output

For each test on a separate line to derive maximum length of increasing subsequences.

Examples