Challenge 24 Electronic Contest Practice

Linear congruential generators (LCGs) are simple random number generators of the form
X_i+1 = (aX_i + c) mod m

LCGs are periodic, because due to "mod m" there will be a smallest P > 0 (the length of the period) where X_i+P = X_i for some i. You have to look at the first P elements of the output from the LCG starting with X₀ = 0. The output of an LCG is the number it provides for our use which we calculate as
Y_i = X_i mod k
where k is yet another constant.

You have to look for repetitions in this list of Y₀ ... Y_P-1. A repetition is a sequence of numbers which occurs in two different positions in this list. For every LCG given in the input you have to output the length of the longest repetition. (Y_i ... Y_i+R-1 is a repetition of length R if there is a j <> i for which Y_i+x = Y_j+x for every x for which 0 <= i + x < P, 0 <= j + x < P and 0 < x < R.)

Input

The first line on the input contains the number of LCGs described in the file. The rest of the file contains one line for every LCG that contains the four numbers a, c, m and k separated by spaces.

Output

Every line of the output file must contain a single number that is the length of the longest repetition. If there are no repetitions (all numbers in Y are different), output 0.

This is the text variant of the problem. Read more here about submitting solutions!

Example

Input
1 1 4 2
Output
2

In this case X = {0, 1, 2, 3}, Y = {0, 1, 0, 1} and the longest repetition is {0, 1}.