题目描述

给定 $N$ 个整数 $A_1, A_2, \dots, A_N$，统计满足以下至少一个条件的三元组 $(x, y, z)$（其中 $1 \le x < y < z \le N$）的个数：

• $A_x = A_y \times A_z$，和/或
• $A_y = A_x \times A_z$，和/或
• $A_z = A_x \times A_y$

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$：数组 $A$ 中整数的个数。第二行包含 $N$ 个整数 $A_i$；其中第 $i$ 个整数表示第 $i$ 个元素的值，如上所述。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是满足题目条件的三元组个数。

4
6
5 2 4 6 3 1
6
2 4 8 16 32 64
3
1 1 1
3
200000 200000 200000

Case #1: 1
Case #2: 6
Case #3: 1
Case #4: 0

提示

在样例 #1 中，唯一满足条件的三元组是 $(2, 4, 5)$。该三元组有效，因为第二个、第四个和第五个整数分别为 $2$、$6$ 和 $3$，且 $2 \times 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 中，不存在满足条件的三元组，因为数组中任意两个数的乘积都不在数组中。

限制条件

$1 \le T \le 30$。

对于所有 $i$，$0 \le A_i \le 2 \times 10^5$。

小数据集（测试集 1 – 可见）

$3 \le N \le 200$。

大数据集（测试集 2 – 隐藏）

$3 \le N \le 7000$。

翻译由 DeepSeek V4 Pro 完成