Максим любит последовательности, особенно те, которые строго возрастают. Сейчас его интересует задача: какова длина самой длинной возрастающей подпоследовательности заданной последовательности a?
Последовательность a задается следующим образом:
- длина последовательности равна n × t;
-
(1 ≤ i ≤ n × t), где операция 
обозначает взятие остатка от деления числа x на число y.
Последовательность s1, s2, ..., sr длины r называется подпоследовательностью последовательности a1, a2, ..., an, если найдется такая возрастающая последовательность индексов i1, i2, ..., ir (1 ≤ i1 < i2 < ... < ir ≤ n), что aij = sj. Иными словами, подпоследовательность может быть получена из последовательности путем вычеркивания некоторых элементов.
Последовательность s1, s2, ..., sr называется возрастающей, если выполняется неравенство: s1 < s2 < ... < sr.
У Максима есть k вариантов последовательности a. Помогите Максиму, для каждой последовательности найдите длину наибольшей возрастающей подпоследовательности.
Выходные данные
Выведите k целых чисел, разделенных пробельными символами — ответы для входных данных. Ответы для каждого варианта последовательности a выводите в порядке следования этих последовательностей во входных данных.