Maxim loves sequences, especially those that strictly increase. He is wondering, what is the length of the longest increasing subsequence of the given sequence $*a*$?

Sequence $*a*$ is given as follows:

• the length of the sequence equals $*n* × *t*$;
• $(1 ≤ *i* ≤ *n* × *t*)$, where operation means taking the remainder after dividing number $*x*$ by number $*y*$.

Sequence $*s*_{1},  *s*_{2},  ...,  *s*_{*r*}$ of length $*r*$ is a subsequence of sequence $*a*_{1},  *a*_{2},  ...,  *a*_{*n*}$, if there is such increasing sequence of indexes $*i*_{1}, *i*_{2}, ..., *i*_{*r*}$ $(1  ≤  *i*_{1}  <  *i*_{2}  < ...   <  *i*_{*r*}  ≤  *n*)$, that $*a*_{*i*_{*j*}}  =  *s*_{*j*}$. In other words, the subsequence can be obtained from the sequence by crossing out some elements.

Sequence $*s*_{1},  *s*_{2},  ...,  *s*_{*r*}$ is increasing, if the following inequality holds: $*s*_{1} < *s*_{2} <  ... <  *s*_{*r*}$.

Maxim have $*k*$ variants of the sequence $*a*$. Help Maxim to determine for each sequence the length of the longest increasing subsequence.

Input

The first line contains four integers $*k*$, $*n*$, $*maxb*$ and $*t*$ $(1 ≤ *k* ≤ 10; 1 ≤ *n*, *maxb* ≤ 10^{5}; 1 ≤ *t* ≤ 10^{9}; *n* × *maxb* ≤ 2·10^{7})$. Each of the next $*k*$ lines contain $*n*$ integers $*b*_{1}, *b*_{2}, ..., *b*_{*n*}$ $(1 ≤ *b*_{*i*} ≤ *maxb*)$.

Note that for each variant of the sequence $*a*$ the values $*n*$, $*maxb*$ and $*t*$ coincide, the only arrays $*b*$s differ.

The numbers in the lines are separated by single spaces.

Output

Print $*k*$ integers — the answers for the variants of the sequence $*a*$. Print the answers in the order the variants follow in the input.