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>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse3,sse4,popcnt,avx,mmx,abm,tune=native")
using namespace std;
namespace output {
void __(short x) { cout << x; }
void __(unsigned x) { cout << x; }
void __(int x) { cout << x; }
void __(long long x) { cout << x; }
void __(unsigned long long x) { cout << x; }
void __(double x) { cout << x; }
void __(long double x) { cout << x; }
void __(char x) { cout << x; }
void __(const char* x) { cout << x; }
void __(const string& x) { cout << x; }
void __(bool x) { cout << (x ? "true" : "false"); }
template <class S, class T>
void __(const pair<S, T>& x) {
  __(1 ? "(" : ""), __(x.first), __(1 ? ", " : " "), __(x.second),
      __(1 ? ")" : "");
}
template <class T>
void __(const vector<T>& x) {
  __(1 ? "{" : "");
  bool _ = 0;
  for (const auto& v : x) __(_ ? 1 ? ", " : " " : ""), __(v), _ = 1;
  __(1 ? "}" : "");
}
template <class T>
void __(const set<T>& x) {
  __(1 ? "{" : "");
  bool _ = 0;
  for (const auto& v : x) __(_ ? 1 ? ", " : " " : ""), __(v), _ = 1;
  __(1 ? "}" : "");
}
template <class T>
void __(const multiset<T>& x) {
  __(1 ? "{" : "");
  bool _ = 0;
  for (const auto& v : x) __(_ ? 1 ? ", " : " " : ""), __(v), _ = 1;
  __(1 ? "}" : "");
}
template <class S, class T>
void __(const map<S, T>& x) {
  __(1 ? "{" : "");
  bool _ = 0;
  for (const auto& v : x) __(_ ? 1 ? ", " : " " : ""), __(v), _ = 1;
  __(1 ? "}" : "");
}
void pr() { cout << "\n"; }
template <class S, class... T>
void pr(const S& a, const T&... b) {
  __(a);
  if (sizeof...(b)) __(' ');
  pr(b...);
}
}  // namespace output
using namespace output;
const int MN = 1e5 + 5, MM = 5000;
int k, n, m, b, t, i, j, x, y, arr[MN], nxt;
map<int, int> mp;
vector<pair<int, int> > dp[MN];
vector<int> pre[MN];
int main() {
  scanf("%d%d%d%d", &k, &n, &b, &t);
  m = min(n, b);
  while (k--) {
    mp.clear();
    nxt = 0;
    for (i = 1; i <= n; i++) {
      scanf("%d", &arr[i]);
      mp[arr[i]] = 0;
    }
    i = 0;
    for (auto it = mp.begin(); it != mp.end(); it++) it->second = ++i;
    for (i = 1; i <= n; i++) arr[i] = mp[arr[i]];
    m = mp.size();
    for (i = 1; i <= m; i++) {
      pre[i].clear();
      pre[i].resize(n + 1);
      int prev = -1;
      for (j = 1; j <= n; j++) {
        if (arr[j] == i) prev = j;
        pre[i][j] = prev;
      }
      for (j = 1; j <= n; j++) {
        if (pre[i][j] == -1) pre[i][j] = prev;
      }
    }
    for (i = 1; i <= m; i++) {
      dp[i].clear();
      dp[i].resize(m + 1);
    }
    dp[m][0] = {n, t};
    dp[m][1] = {pre[m][n], t};
    int ans = 0;
    for (i = m; i >= 1; i--) {
      for (j = 0; j <= m; j++) {
        if (dp[i][j].first || dp[i][j].second) {
          ans = max(ans, j);
          if (i > 1) {
            int nx = pre[i - 1][dp[i][j].first], ny = dp[i][j].second;
            if (nx > dp[i][j].first) ny--;
            if (ny >= 1) {
              if (ny > dp[i - 1][j + 1].second)
                dp[i - 1][j + 1] = {nx, ny};
              else if (ny == dp[i - 1][j + 1].second &&
                       nx > dp[i - 1][j + 1].first)
                dp[i - 1][j + 1] = {nx, ny};
            }
            nx = dp[i][j].first, ny = dp[i][j].second;
            if (ny > dp[i - 1][j].second)
              dp[i - 1][j] = {nx, ny};
            else if (ny == dp[i - 1][j].second && nx > dp[i - 1][j].first)
              dp[i - 1][j] = {nx, ny};
          }
        }
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}
