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 pair<int, int> bound(0, 0);
int main() {
  int k, n, maxb, t;
  scanf("%d%d%d%d", &k, &n, &maxb, &t);
  while (k--) {
    vector<int> seq(n);
    vector<vector<pair<int, int>>> dp(
        n + 1, vector<pair<int, int>>(maxb + 1, make_pair(0, 0)));
    vector<pair<int, int>> early(maxb + 1, make_pair(987654321, 987654321));
    vector<vector<int>> follower(n, vector<int>(maxb + 1, 987654321));
    vector<int> first(maxb + 1, 987654321);
    for (int i = 0; i < n; i++) scanf("%d", &seq[i]);
    for (int i = 0; i < n; i++) first[seq[i]] = min(first[seq[i]], i);
    follower[0] = first;
    int f = seq[0];
    follower[0][f] = 987654321;
    for (int i = 1; i < n; i++) {
      if (seq[i] == f) {
        follower[0][f] = i;
        break;
      }
    }
    for (int i = 1; i < n; i++) {
      for (int j = 1; j <= maxb; j++) {
        if (seq[i] != j) {
          follower[i][j] = follower[i - 1][j];
        } else {
          for (int k = i + 1; k < n; k++)
            if (seq[k] == j) {
              follower[i][j] = k;
              break;
            }
        }
      }
    }
    for (int i = 0; i < n; i++)
      early[seq[i]] = make_pair(1, min(early[seq[i]].second, i));
    for (int j = 2; j <= maxb; j++) early[j] = min(early[j - 1], early[j]);
    for (int i = 1; i <= maxb; i++)
      if (first[i] < n) dp[1][i] = make_pair(1, first[i]);
    for (int i = 2; i <= n; i++) {
      for (int j = maxb; j > 0; j--) {
        early[j] = make_pair(987654321, 987654321);
        if (first[j] == 987654321) continue;
        pair<int, int> beforePos = early[j - 1];
        if (beforePos.first == 987654321) continue;
        int nextPos = follower[beforePos.second][j];
        if (nextPos == 987654321) {
          if (beforePos.first < t) {
            dp[i][j] = make_pair(beforePos.first + 1, first[j]);
          }
        } else {
          dp[i][j] = make_pair(beforePos.first, nextPos);
        }
        if (dp[i][j] != bound) early[j] = dp[i][j];
      }
      for (int j = 2; j <= maxb; j++) early[j] = min(early[j - 1], early[j]);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= maxb; j++) {
        if (dp[i][j] != bound) ans = i;
      }
    }
    printf("%d\n", ans);
  }
}
