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 ; (1 ≤ i ≤ n × t), where operation means taking the remainder after dividing number x by number y . Sequence s 1, s 2, ..., s r of length r is a subsequence of sequence a 1, a 2, ..., a n , if there is such increasing sequence of indexes i 1, i 2, ..., i r (1 ≤ i 1 i 2 i r ≤ n), that a i j = s j . In other words, the subsequence can be obtained from the sequence by crossing out some elements. Sequence s 1, s 2, ..., s r is increasing, if the following inequality holds: s 1 s 2 s r . Maxim have k variants of the sequence a . Help Maxim to determine for each sequence the length of the longest increasing subsequence.

输入描述:

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.

输出描述:

Print k integers — the answers for the variants of the sequence a. Print the answers in the order the variants follow in the input.