НВП

Містер C зацікавився задачею пошуку Найдовшої Зростаючої Підпослідовності. Нехай дана послідовність (S = s_1, s_2, ..., s_n). Найдовша Зростаюча Підпослідовність — це така підпослідовність (L = l_1, l_2, ..., l_k) з (S), що (l_1 < l_2 < ...< l_k).

Для заданої послідовності (S) потрібно знайти сумарну довжину НЗП для кожної підпослідовності (S) ненульової довжини, в якій елементи розташовані послідовно!

Вхідні дані

Перший рядок містить кількість тестів (t). Далі йдуть (t) тестів.

Перший рядок кожного тесту містить довжину (n) ((1 $\le$ n $\le$ 500)) послідовності (S). Кожен з наступних (n) рядків містить ціле число (s_i) ((1 $\le$ s_i $\le$ n)) — (i)-й елемент (S). Усі елементи (S) різні.

Вихідні дані

Виведіть (t) рядків, по одному для кожного тесту.

Кожен рядок має формат "Case #i: S", де (i) — номер тесту, (S) — загальна довжина НЗП усіх послідовних підпослідовностей (S).

Приклади