ACM-ICPC Indonesia National Contest 2016

Problem G

Beautiful Triple

Time Limit: 2 seconds

In a sequence of N integers A1..N, a triple ⟨a, b, c⟩ is considered beautiful if Aa = Ac and 1 ≤ a < b < c ≤ N.

For example, a sequence A1..6 = {3, 1, 3, 7, 3, 7} has 6 beautiful triples:

Given a sequence of integers, determine how many beautiful triples are there in the sequence. Modulo the output with 1,000,000,007.


Input

The first line of input contains an integer T (T ≤ 50) denoting the number of cases. Each case begins with an integer N (1 ≤ N ≤ 100,000) denoting the size of the integer sequence. The next line contains N integers Ai (1 ≤ Ai ≤ 100,000) representing the elements in A, for i = 1..N respectively.

Output

For each case, output in a line "Case #X: Y" where X is the case number, starts from 1, and Y is the output for that particular case.


Sample InputOutput for Sample Input
4
6
3 1 3 7 3 7
3
5 5 5
7
35 35 35 35 35 35 35
4
102 38 173 25
Case #1: 6
Case #2: 1
Case #3: 35
Case #4: 0