Beautiful Triple

In a sequence of N integers A_1..N, a triple ⟨a, b, c⟩ is considered beautiful if A_a = A_c and 1 ≤ a < b < c ≤ N.

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

• ⟨1, 2, 3⟩ – A₁ = 3, A₂ = 1, A₃ = 3.
• ⟨1, 2, 5⟩ – A₁ = 3, A₂ = 1, A₅ = 3.
• ⟨1, 3, 5⟩ – A₁ = 3, A₃ = 3, A₅ = 3.
• ⟨1, 4, 5⟩ – A₁ = 3, A₄ = 7, A₅ = 3.
• ⟨3, 4, 5⟩ – A₁ = 3, A₄ = 7, A₅ = 3.
• ⟨4, 5, 6⟩ – A₄ = 7, A₅ = 3, A₆ = 7.

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 A_i (1 ≤ A_i ≤ 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.

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