The 21st century introduces the multicores. As a result a research is going on in parallel Computing. With time the number of processor would grow very large. As of now, Professor Biloo at IIIT asks a student to implement the following code on multiple G-line processors.

        for(i=1;i<=x;i++){
                for(j=1;j<=x;j++){
                        for(k=1;k<=a;k++){
                                z=z%y;
                        }
                }
                for(j=1;j<=b;j++){
                        z=z/y;
                }
        }
        for(i=1;i<=c;i++){
                z=z%y;
        }

The students experiments and finds that the only significant operations are the modulus(%) and division(/) operation which take almost equal time. The time taken by other operations may be ignored in the order analysis. He finds a algorithm to solve the problem in which these operations can be carried out in random order. For his testing he chooses M processors . Each processor will carry out exactly M operations (% or /) .The performance is optimal when such a scheme exactly covers all the operations.

Puzzled, the student finds that this can only be done for some specific values of x for given a, b and c. He wants to trick the professor, so he needs few values of x for which his algorithm works. However, to make the professor feel that he manually did it these values of x need to be as small as possible.

Given the values of a, b, c and k, output the first k values of x, for which the student's algorithm works.

Note: The value of x should be greater than or equal to 0.

Input

The first line of input contains an integer t , the number of testcases. For each testcase , there is exactly one line which contains 4 space separated a, b, c and k.

Output

For each test case, output the corresponding k values of x, each in successive different lines.

Example

Input:
1
1 2 1 4

Output:
0
1
2
3

Constraints and Limits

t ≤ 10. The values in the output vi ≤ 10^12. Each of the intermediate values will fit in a 64 bit variable. The values a, b, c would be such that 0 ≤ a, b, c ≤ 100 and b^2-4ac ≥ 0. k ≤ 1000.

Note: Test data to this problem was modified on Feb 7.
Note 2: There were some mistakes in the test data discovered on March 11, 2008. New tricky cases provided by Blue Mary are also put up now and some "Accepted" solutions have received wrong answer. My apologies to one and all for the mistakes.