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;
struct val {
  int t, i;
  val(int a = 1 << 25, int b = 1 << 25) { t = a, i = b; }
  void init() { t = i = 1 << 25; }
  bool operator<(const val &v) {
    if (t != v.t) return t < v.t;
    return i < v.i;
  }
};
const int MAXB = 100005;
val dp[2][MAXB];
int b[100005];
int Z[100005];
vector<int> ID[100005];
int main() {
  if (!1)
    freopen(
        ""
        ".in",
        "r", stdin);
  if (!1)
    freopen(
        ""
        ".out",
        "w", stdout);
  int i, j, k, _T, n, maxb, t;
  while (~scanf("%d%d%d%d", &_T, &n, &maxb, &t))
    while (_T--) {
      for (i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
        Z[i - 1] = b[i];
      }
      sort(Z, Z + n);
      int nz = unique(Z, Z + n) - Z;
      for (i = 1; i <= n; i++) b[i] = lower_bound(Z, Z + nz, b[i]) - Z;
      for (i = 0; i < nz; i++) ID[i].clear();
      for (i = 1; i <= n; i++) ID[b[i]].push_back(i);
      for (i = 1; i <= n; i++)
        if (val(1, i) < dp[1][b[i]]) dp[1][b[i]] = val(1, i);
      int ans = 1;
      for (j = 2; j <= nz; j++) {
        int x = (j - 1) & 1, y = j & 1;
        for (i = 0; i < nz; i++) dp[y][i].init();
        val b;
        for (i = 0; i < nz; i++) {
          for (k = 0; k < ID[i].size(); k++) {
            int id = ID[i][k];
            val next = b;
            if (next.i < id)
              next.i = id;
            else
              next = val(next.t + 1, id);
            if (next < dp[y][i]) dp[y][i] = next;
          }
          if (dp[x][i] < b) b = dp[x][i];
        }
        for (i = 0; i < nz; i++)
          if (dp[y][i].t <= t) ans = max(ans, j);
        if (ans < j) break;
      }
      cout << ans << "\n";
    }
  return 0;
}
