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.*;
import java.util.*;

public class D_submit_fromcustomtest {

	BufferedReader br;
	PrintWriter out;
	StringTokenizer st;
	boolean eof;

	void solve() throws IOException {
		int tests = nextInt();
		int n = nextInt();
		int maxB = nextInt();
		int rep = nextInt();
		
		int[] a = new int[n];
		
		int[] map = new int[maxB];
		int mapVer = 0;
		
		int[] mapToSmall = new int[maxB];	
		
		int[] d = new int[maxB + 1];
		
		//long start = System.currentTimeMillis();
		
		testStart: while (tests-- > 0) {
			
			//long now = System.currentTimeMillis();
			//System.err.println("prev iteration took " + (now - start));
			//start = now;
			
			mapVer++;
			
			int cntDiff = 0;
			
			for (int i = 0; i < n; i++) {
				int x = a[i] = nextInt() - 1;
				if (map[x] != mapVer) {
					cntDiff++;
					map[x] = mapVer;
				}
			}
			
			if (rep >= cntDiff) {
				out.println(cntDiff);
				continue testStart;
			}
			
			for (int i = 0, j = 0; i < maxB; i++)
				if (map[i] == mapVer) {
					mapToSmall[i] = j++;
				}
			
//			System.err.println(Arrays.toString(mapToSmall));
			
			for (int i = 0; i < n; i++)
				a[i] = mapToSmall[a[i]];
			
			Arrays.fill(d, maxB);
			d[0] = -1;
			
			int curLen = 0;
			
			for (int i = 0; i < rep; i++) // now d[i] = i - 1 and never change again!
				for (int j = 0; j < n; j++) {
					int x = a[j];
					if (x < i)
						continue;
					
					int low = i; // d[low] < x
					int high = curLen + 1; // d[high] >= x
					while (low < high - 1) {
						int mid = (low + high) >> 1;
						if (d[mid] < x)
							low = mid;
						else
							high = mid;
					}
					d[high] = x;
					if (high == curLen + 1) {
						curLen++;
						if (curLen == cntDiff) {
							out.println(cntDiff);
							continue testStart;
						}
					}
				}
			out.println(curLen);
		}
	}

	D_submit_fromcustomtest() throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		solve();
		out.close();
	}

	public static void main(String[] args) throws IOException {
		new D_submit_fromcustomtest();
	}

	String nextToken() {
		while (st == null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				eof = true;
				return null;
			}
		}
		return st.nextToken();
	}

	String nextString() {
		try {
			return br.readLine();
		} catch (IOException e) {
			eof = true;
			return null;
		}
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
}