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;
const int MOD = 1000000007;
const int UNDEF = -1;
const long long INF = 1e18;
template <typename T>
inline bool chkmax(T &aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T &aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
int rint();
char rch();
long long rlong();
void makeunique(vector<int> &vx) {
  sort(vx.begin(), vx.end());
  auto it = unique(vx.begin(), vx.end());
  vx.resize(std::distance(vx.begin(), it));
}
int bins(vector<int> &vx, int x) {
  int imin = 0, imax = vx.size();
  while (imin < imax) {
    int imid = (imin + imax) >> 1;
    if (vx[imid] < x)
      imin = imid + 1;
    else
      imax = imid;
  }
  return imin;
}
const int mn = 2e7 + 2;
int f[mn];
int longest_strictly_increasing_subsequence(vector<int> &p, int maxval,
                                            int repeats) {
  memset(f, 0, sizeof(int) * (maxval + 1));
  for (int r = 0; r < repeats; r++) {
    for (auto &x : p) {
      int best = f[x - 1] + 1;
      for (int y = x; y <= maxval; y++) {
        if (f[y] < best)
          f[y] = best;
        else
          break;
      }
    }
  }
  return f[maxval];
}
int compress(vector<int> &vinp) {
  vector<int> bintable = vinp;
  makeunique(bintable);
  for (auto &w : vinp) {
    w = bins(bintable, w) + 1;
  }
  return (int)bintable.size();
}
int n, t;
vector<int> b;
void solve() {
  for (int i = 0; i < n; i++) b[i] = rint();
  int maxval = compress(b);
  int ans = longest_strictly_increasing_subsequence(b, maxval, min(t, maxval));
  printf("%d\n", ans);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int numtests, maxb;
  numtests = rint(), n = rint(), maxb = rint(), t = rint();
  b.resize(n);
  for (int test = 0; test < numtests; test++) solve();
}
static char stdinBuffer[1024];
static char *stdinDataEnd = stdinBuffer + sizeof(stdinBuffer);
static const char *stdinPos = stdinDataEnd;
void readAhead(size_t amount) {
  size_t remaining = stdinDataEnd - stdinPos;
  if (remaining < amount) {
    memmove(stdinBuffer, stdinPos, remaining);
    size_t sz = fread(stdinBuffer + remaining, 1,
                      sizeof(stdinBuffer) - remaining, stdin);
    stdinPos = stdinBuffer;
    stdinDataEnd = stdinBuffer + remaining + sz;
    if (stdinDataEnd != stdinBuffer + sizeof(stdinBuffer)) *stdinDataEnd = 0;
  }
}
int rint() {
  readAhead(16);
  int x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}
char rch() {
  readAhead(16);
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  char ans = *stdinPos;
  ++stdinPos;
  return ans;
}
long long rlong() {
  readAhead(32);
  long long x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}
