LIS
Mr. C is interested with Longest Increasing Subsequence problem. Given a sequence S = s_1, s_2, …, s_N. The Longest Increasing Subsequence is the subsequence L = l_1, l_2, …, l_k of S such that l_1 < l_2 < … < l_k.
Given a sequence S, find the total length of LIS of every consecutive subsequence (subsequence which elements are consecutive in the original sequence) of S with non zero length!
Input
The first line of input consists of an integer t denotes the number of cases. It is followed by t blocks, each representing a case.
The first line of each case contains an integers: n (1 ≤ n ≤ 500), the length of S.
The next N lines each consists of an integer s_i (1 ≤ s_i ≤ n) denoting the i-th element of S. Each element of S is unique.
Output
Output consists of 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 "Case #i: S", where i represents the case number and S represents the total length of LIS of every consecutive subsequence of S.