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;
long long int powmod(long long int a, int b, int n) {
  long long int rm = 1;
  while (b) {
    if (b % 2) {
      rm = (rm * a) % n;
    }
    a = (a * a) % n;
    b /= 2;
  }
  return rm;
}
int dp[int(1e5 + 10)] = {0}, uni[int(1e5 + 10)] = {0}, b[int(1e5 + 10)],
                 nowdp[int(1e5 + 10)];
int BITree[100100] = {0}, n, g[int(1e5 + 10)], N;
int getmax(int index) {
  int mx = 0;
  while (index > 0) {
    mx = max(mx, BITree[index]);
    index -= index & (-index);
  }
  return mx;
}
void updateBIT(int index, int val) {
  while (index <= N) {
    if (BITree[index] >= val) return;
    BITree[index] = val;
    index += index & (-index);
  }
}
int main() {
  int k, maxb, t;
  cin >> k >> n >> maxb >> t;
  N = maxb;
  for (int u = int(1); u <= (int)k; u++) {
    for (int i = int(1); i <= (int)n; i++) {
      scanf("%d", &b[i]);
      ;
    }
    memset(dp, 0, sizeof(dp));
    ;
    memset(BITree, 0, sizeof(BITree));
    ;
    if (t >= n) {
      int dis = 0;
      for (int i = int(1); i <= (int)n; i++)
        if (uni[b[i]] != u) uni[b[i]] = u, dis++;
      cout << dis << endl;
      continue;
    }
    for (int i = 1; i <= t; ++i) {
      int cd = 0;
      for (int j = 1; j <= n; ++j) {
        if (b[j] > 1)
          nowdp[b[j]] = 1 + getmax(b[j] - 1);
        else
          nowdp[b[j]] = 1;
        if (nowdp[b[j]] > dp[b[j]]) {
          dp[b[j]] = nowdp[b[j]];
          cd = 1;
          updateBIT(b[j], dp[b[j]]);
        }
      }
      if (!cd) break;
    }
    int ans = 0;
    for (int i = 1; i <= maxb; ++i) {
      ans = max(ans, dp[i]);
    }
    cout << ans << endl;
  }
  return 0;
}
