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; 
  * <image> (1 ≤ i ≤ n × t), where operation <image> means taking the remainder after dividing number x by number y. 



Sequence s1, s2, ..., sr of length r is a subsequence of sequence a1, a2, ..., an, if there is such increasing sequence of indexes i1, i2, ..., ir (1 ≤ i1 < i2 < ... < ir ≤ n), that aij = sj. In other words, the subsequence can be obtained from the sequence by crossing out some elements.

Sequence s1, s2, ..., sr is increasing, if the following inequality holds: s1 < s2 < ... < sr.

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 ≤ 105; 1 ≤ t ≤ 109; n × maxb ≤ 2·107). Each of the next k lines contain n integers b1, b2, ..., bn (1 ≤ bi ≤ maxb). 

Note that for each variant of the sequence a the values n, maxb and t coincide, the only arrays bs 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.

Examples

Input

3 3 5 2
3 2 1
1 2 3
2 3 1


Output

2
3
3
import java.util.List;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Random;
import java.io.Reader;
import java.io.Writer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Niyaz Nigmatullin
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		FastScanner in = new FastScanner(inputStream);
		FastPrinter out = new FastPrinter(outputStream);
		TaskD solver = new TaskD();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskD {
    public void solve(int testNumber, FastScanner in, FastPrinter out) {
        int k = in.nextInt();
        int n = in.nextInt();
        int maxb = in.nextInt();
        int t = in.nextInt();
        for (int test = 0; test < k; test++) {
            int[] b = in.readIntArray(n);
            int[] c = ArrayUtils.sortAndUnique(b);
            for (int i = 0; i < n; i++) {
                b[i] = Arrays.binarySearch(c, b[i]);
            }
            if (t >= c.length) {
                out.println(c.length);
                continue;
            }
            int[] where = new int[c.length];
            for (int it = 0; it < t; it++) {
                for (int i : b) {
                    int z = i == 0 ? 0 : where[i - 1];
                    for (int j = i; j < c.length && where[j] == z; j++) {
                        where[j]++;
                    }
                }
            }
            int answer = 0;
            for (int i : where) {
                answer = Math.max(answer, i);
            }
            out.println(answer);
        }
    }
}

class FastScanner extends BufferedReader {

    boolean isEOF;

    public FastScanner(InputStream is) {
        super(new InputStreamReader(is));
    }

    public int read() {
        try {
            int ret = super.read();
            if (isEOF && ret < 0) {
                throw new InputMismatchException();
            }
            isEOF = ret == -1;
            return ret;
        } catch (IOException e) {
            throw new InputMismatchException();
        }
    }

    static boolean isWhiteSpace(int c) {
        return c >= -1 && c <= 32;
    }

    public int nextInt() {
        int c = read();
        while (isWhiteSpace(c)) {
            c = read();
        }
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int ret = 0;
        while (!isWhiteSpace(c)) {
            if (c < '0' || c > '9') {
                throw new NumberFormatException("digit expected " + (char) c
                        + " found");
            }
            ret = ret * 10 + c - '0';
            c = read();
        }
        return ret * sgn;
    }

    public int[] readIntArray(int n) {
        int[] ret = new int[n];
        for (int i = 0; i < n; i++) {
            ret[i] = nextInt();
        }
        return ret;
    }

    }

class FastPrinter extends PrintWriter {

    public FastPrinter(OutputStream out) {
        super(out);
    }

    public FastPrinter(Writer out) {
        super(out);
    }


}

class ArrayUtils {

    static public int[] sortAndUnique(int[] a) {
        int[] ret = a.clone();
        sort(ret);
        if (ret.length == 0) {
            return ret;
        }
        int last = ret[0];
        int j = 1;
        for (int i = 1; i < ret.length; i++) {
            if (last != ret[i]) {
                ret[j++] = ret[i];
            }
            last = ret[i];
        }
        return Arrays.copyOf(ret, j);
    }

    public static void sort(int[] a) {
        Random rand = new Random(System.nanoTime());
        for (int i = 0; i < a.length; i++) {
            int j = rand.nextInt(i + 1);
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        Arrays.sort(a);
    }


    }

