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.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.util.ArrayList;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Random;
import java.io.Writer;
import java.math.BigInteger;
import java.io.InputStream;

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

class TaskD {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
		int k = in.readInt();
		int n = in.readInt();
		int maxb = in.readInt();
		int t = in.readInt();
		while (k > 0) {
			k --;
			int[] a = in.readIntArray(n);
			int[] axis = Arrays.copyOf(a, n);
			ArrayUtil.sort(axis);
			axis = ArrayUtil.unique(axis);
			if (t >= axis.length) {
				out.printLine(axis.length);
				continue;
			}
			for (int i = 0; i < n; i ++) {
				a[i] = Arrays.binarySearch(axis, a[i]);
			}
			int[] f = new int[axis.length];
			Arrays.fill(f, 0);
			for (int tt = 0; tt < t; tt ++) {
				for (int i = 0; i < n; i ++) {
					int tmp = (a[i] == 0) ? 0 : f[a[i] - 1];
					int j = a[i];
					while (j < axis.length && f[j] == tmp) {
						f[j] ++;
						j ++;
					}
				}
			}
			out.printLine(f[axis.length - 1]);
		}
    }
}

class InputReader {
	private InputStream stream;
	private byte[] buf = new byte[1000];
	private int curChar;
	private int numChars;

	public InputReader(InputStream stream) {
		this.stream = stream;
	}

	private int read() {
		if (numChars == -1)
			throw new UnknownError();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new UnknownError();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int readInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9') throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] readIntArray(int length) {
		int[] res = new int[length];
		for (int i = 0; i < length; i ++) res[i] = readInt();
		return res;
	}

	private boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}
}

class OutputWriter {
	private final PrintWriter writer;

	public OutputWriter(OutputStream outputStream) {
		writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
	}

	public OutputWriter(Writer writer) {
		this.writer = new PrintWriter(writer);
	}

	public void print(Object...objects) {
		for (int i = 0; i < objects.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}

	public void printLine(Object...objects) {
		print(objects);
		writer.println();
	}

	public void close() {
		writer.close();
	}
}

class ArrayUtil {
	private ArrayUtil() {
	}

	public static int[] unique(int[] data) {
		if (data.length == 0) return data;
		for (int i = 0; i < data.length - 1; i ++)
			if (data[i] > data[i + 1]) throw new RuntimeException();
		ArrayList<Integer> l = new ArrayList<Integer>();
		l.add(data[0]);
		for (int i = 1; i < data.length; i ++)
			if (data[i] != l.get(l.size() - 1)) l.add(data[i]);
		int[] res = new int[l.size()];
		for (int i = 0; i < l.size(); i ++) res[i] = l.get(i);
		return res;
	}

	private static void swap(int[] data, int i, int j) {
		int tmp = data[i];
		data[i] = data[j];
		data[j] = tmp;
	}

	private static void quickSort(int[] data, int l, int r, Random rnd) {
		int x = rnd.nextInt(r - l + 1) + l;
		swap(data, (l + r) / 2, x);
		int mid = data[(l + r) / 2];
		int i = l, j = r;
		do {
			while (data[i] < mid) i ++;
			while (data[j] > mid) j --;
			if (i <= j) {
				swap(data, i, j);
				i ++;
				j --;
			}
		} while (i <= j);
		if (l < j) quickSort(data, l, j, rnd);
		if (i < r) quickSort(data, i, r, rnd);
	}

	public static void sort(int[] data) {
		quickSort(data, 0, data.length - 1, new Random());
	}

	}

