НВП#6378
Містер C зацікавився задачею пошуку Найдовшої Зростаючої Підпослідовності. Нехай дана послідовність S = s_1, s_2, \ldots, s_n. Найдовша Зростаюча Підпослідовність — це така підпослідовність L = l_1, l_2, \ldots, l_k з , що l_1 < l_2 < \ldots < l_k.
Для заданої послідовності потрібно знайти сумарну довжину НЗП для кожної підпослідовності ненульової довжини, в якій елементи розташовані послідовно!
Перший рядок містить кількість тестів . Далі йдуть тестів.
Перший рядок кожного тесту містить довжину (1 \leq n \leq 500) послідовності . Кожен з наступних рядків містить ціле число s_i (1 \leq s_i \leq n) — -й елемент . Усі елементи різні.
Виведіть рядків, по одному для кожного тесту.
Кожен рядок має формат "Case #i: S", де i — номер тесту, S — загальна довжина НЗП усіх послідовних підпослідовностей .
Приклад 1