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.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.InputStream;

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

class TaskD {

    class Order {

        private int arr[];

        Order(int orig[]) {
            int temp[] = orig.clone();
            Arrays.sort(temp);

            int total = 1;
            for (int i = 1; i < temp.length; ++i)
                if (temp[i] != temp[i - 1])
                    ++total;

            arr = new int[total];
            arr[0] = temp[0];
            total = 1;
            for (int i = 1; i < temp.length; ++i)
                if (temp[i] != temp[i - 1])
                    arr[total++] = temp[i];
        }

        public int size() {
            return arr.length;
        }

        public int get(int x) {
            return Arrays.binarySearch(arr, x);
        }

        }

    private int solve(InputReader in, int n, int t) {
        int a[] = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = in.nextInt();
        }

        Order order = new Order(a);
        int maxAnswer = order.size();
        for (int i = 0; i < n; ++i) {
            a[i] = order.get(a[i]);
        }

        int ans = 0;
        int minValue[] = new int[maxAnswer + 1];
        Arrays.fill(minValue, Integer.MAX_VALUE);
        minValue[0] = -1;

        int ptrLast[] = new int[n];

        for (int round = 0; round < t && round < maxAnswer && ans < maxAnswer; ++round) {
            for (int i = 0; i < n && ans < maxAnswer; ++i) {
                while (minValue[ptrLast[i]] < a[i]) {
                    ++ptrLast[i];
                }

                if (a[i] < minValue[ptrLast[i]]) {
                    minValue[ptrLast[i]] = a[i];
                }

                ans = Math.max(ans, ptrLast[i]);
            }
        }

        return ans;
    }

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int k = in.nextInt();
        int n = in.nextInt();
        int maxb = in.nextInt();
        int t = in.nextInt();

        for (int i = 1; i <= k; ++i) {
            out.println(solve(in, n, t));
        }
    }
}

class InputReader {
    BufferedReader reader;
    StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    }
