곱 삼중항

N개의 정수 $A_{1}$, $A_{2}$, ..., $A_{N}$가 주어질 때, 다음 중 적어도 하나가 참인 삼중항 (x, y, z) (단, 1 ≤ x < y < z ≤ N)의 수를 센다.

• $A_{x}$ = $A_{y}$ × $A_{z}$, 및/또는

• $A_{y}$ = $A_{x}$ × $A_{z}$, 및/또는

• $A_{z}$ = $A_{x}$ × $A_{y}$

제한

1 ≤ T ≤ 30. 테스트 세트당 시간 제한: 40초. 메모리 제한: 1 GB. 모든 i에 대해, 0 ≤ $A_{i}$ ≤ 2 × $10^{5}$.

작은 데이터 세트 (테스트 세트 1 - 공개)

3 ≤ N ≤ 200.

큰 데이터 세트 (테스트 세트 2 - 비공개)

3 ≤ N ≤ 7000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 배열 A에 있는 정수의 수를 나타내는 정수 N이 담긴 한 줄로 시작한다. 두 번째 줄은 N개의 정수 $A_{i}$로 이루어지며, 이 중 i번째 값은 위에서 설명한 i번째 정수의 값이다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y은 문제 설명에 주어진 조건을 만족하는 삼중항의 수이다.

예제 케이스 #1에서 문제 설명에 주어진 조건을 만족하는 유일한 삼중항은 (2, 4, 5)이다. 두 번째, 네 번째, 다섯 번째 정수가 각각 2, 6, 3이고, 2 × 3 = 6이므로 이 삼중항은 유효하다.

예제 케이스 #2에서 문제 설명에 주어진 조건을 만족하는 여섯 개의 삼중항은 다음과 같다: (1, 2, 3), (1, 3, 4), (1, 4, 5), (1, 5, 6), (2, 3, 5), (2, 4, 6).

예제 케이스 #3에서는 삼중항 (1, 2, 3)을 한 번만 세어야 한다.

예제 케이스 #4에서는 배열에 있는 어떤 두 정수를 곱해도 그 곱이 배열에 존재하지 않으므로, 문제 설명에 주어진 조건을 만족하는 삼중항이 없다.