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;
template <class T>
inline void umax(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
inline void umin(T &a, T b) {
  if (a > b) a = b;
}
template <class T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
template <class T>
inline T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
const int inf = 1e9 + 143;
inline int read() {
  int x;
  scanf(" %d", &x);
  return x;
}
const int N = 101001;
const int B = 4500;
int n, maxb, t;
int b[N];
int f[B];
void solve() {
  for (int i = 0; i < B; i++) f[i] = 0;
  for (int i = 0; i < n; i++) {
    b[i] = 0;
    int c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
      b[i] = b[i] * 10 + c - '0';
      c = getchar();
    }
  }
  vector<int> vals;
  for (int i = 0; i < n; i++) vals.push_back(b[i]);
  sort(vals.begin(), vals.end());
  vals.erase(unique(vals.begin(), vals.end()), vals.end());
  for (int i = 0; i < n; i++)
    b[i] = lower_bound(vals.begin(), vals.end(), b[i]) - vals.begin() + 1;
  int nn = vals.size();
  int len = min((int)vals.size(), t) * n;
  register int x, r;
  for (register int i = 0; i < len; i++) {
    int bb = b[i % n];
    if (bb >= i / n) {
      x = bb - 1;
      r = 0;
      while (x > 0) {
        if (r < f[x]) r = f[x];
        x -= x & -x;
      }
      x = bb;
      ++r;
      while (x < nn + 1) {
        if (f[x] < r) f[x] = r;
        x += x & -x;
      }
    }
  }
  int ans = 0;
  x = nn;
  while (x > 0) {
    umax(ans, f[x]);
    x -= x & -x;
  }
  printf("%d\n", ans);
}
int main() {
  int k = read();
  n = read();
  maxb = read();
  t = read();
  for (int i = 0; i < k; i++) {
    solve();
  }
  return 0;
}
