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
#include <bits/stdc++.h>
using namespace std;
int d[2 * 8192], b[100100], p;
map<int, int> m;
map<int, int>::iterator it;
int get(int j) {
  int i, r = 0;
  for (i = p, j += p; i <= j; i >>= 1, j = (j - 1) >> 1)
    if ((~j & 1) && d[j] > r) r = d[j];
  return r;
}
void ins(int i, int v) {
  for (i += p; i > 0 && d[i] < v; d[i] = v, i >>= 1)
    ;
}
int main() {
  int i, j, k, n, t, q, w;
  scanf("%d%d%d%d", &q, &n, &w, &t);
  t = min(t, min(n, w));
  for (; q--;) {
    m.clear();
    for (i = 0; i < n; scanf("%d", &b[i]), m[b[i]] = 1, i++)
      ;
    for (it = m.begin(), i = 0; it != m.end(); it->second = i, i++, it++)
      ;
    for (i = 0; i < n; b[i] = m[b[i]], i++)
      ;
    for (p = 1; p < m.size(); p *= 2)
      ;
    for (i = 0; i < 2 * p; d[i] = 0, i++)
      ;
    for (i = 0; i < n * t && d[1] < w; i++) {
      j = b[i % n];
      if (i + (w - j) * n < n * t) continue;
      if (d[p + j] == j + 1) continue;
      k = get(j - 1) + 1;
      if (d[p + j] == k) continue;
      ins(j, k);
    }
    printf("%d\n", d[1]);
  }
  return 0;
}
