Problems
LIS
LIS
Mr. C is interested with Longest Increasing Subsequence problem. Given a sequence \textbf{S = s_1, s_2, …, s_N}. The Longest Increasing Subsequence is the subsequence \textbf{L = l_1, l_2, …, l_k} of \textbf{S} such that \textbf{l_1} < \textbf{l_2} < … < \textbf{l_k}.
Given a sequence \textbf{S}, find the total length of \textbf{LIS} of every consecutive subsequence (subsequence which elements are consecutive in the original sequence) of \textbf{S} with non zero length!
\InputFile
The first line of input consists of an integer \textbf{t }denotes the number of cases. It is followed by \textbf{t }blocks, each representing a case.
The first line of each case contains an integers: \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{500}), the length of \textbf{S}.
The next \textbf{N} lines each consists of an integer \textbf{s_i} (\textbf{1 }≤ \textbf{s_i} ≤ \textbf{n}) denoting the \textbf{i}-th element of \textbf{S}. Each element of \textbf{S }is unique.
\OutputFile
Output consists of \textbf{t }lines, each describes the solution for each case with the same order as in input.
Each case consists of a single line with the format "\textbf{Case #i: S}", where \textbf{i} represents the case number and \textbf{S} represents the total length of \textbf{LIS} of every consecutive subsequence of \textbf{S}.
Input example #1
1 3 3 1 2
Output example #1
Case #1: 8