由于下赛季即将到来,您希望组建一支由两到三名参与者组成的团队。有 $$$n$$$ 个候选人,第 $$$i$$$ 个候选人的排名为 $$$a_i$$$。但是你对你的队友有奇怪的要求:如果你的排名是$$$v$$$并且选择了第$$$i$$$和第$$$j$$$个候选人,那么必须满足$$$GCD(v, a_i) = X$$$和$$$LCM(v, a_j) = Y$$$。
你非常有经验,所以你可以将你的排名更改为任何非负整数,但 $$$X$$$ 和 $$$Y$$$ 与你的出生日期相关,所以它们是固定的。
现在你想知道,有多少对 $$$(i, j)$$$ 使得存在满足以下约束的整数 $$$v$$$:$$$GCD(v, a_i) = X$$$ 和 $$$LCM(v, a_j) = Y$$$。有可能$$$i = j$$$ 并且你们组成了一个两人团队。
$$$GCD$$$ 是两个数字的最大公约数,$$$LCM$$$ — 最小公倍数。
输入
第一行包含三个整数 $$$n$$$、$$$X$$$ 和 $$$Y$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le X \le Y \le 10^{18}$$$) — 候选者的数量和相应的常量。
第二行包含 $$$n$$$ 空格分隔的整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{18}$$$) — 候选人的排名。
输出
打印唯一的整数 - $$$(i, j)$$$ 对的数量,使得存在满足以下约束的整数 $$$v$$$:$$$GCD(v, a_i) = X$$$ 和 $$$LCM(v, a_j) = Y$$$。有可能 $$$i = j$$$。
示例
输入 #1
12 2 2 1 2 3 4 5 6 7 8 9 10 11 12
输出 #1
12
输入 #2
12 1 6 1 3 5 7 9 11 12 10 8 6 4 2
输出 #2
30
注意
在第一个示例中,接下来的对是有效的:$$$a_j = 1$$$ 和 $$$a_i = [2, 4, 6, 8, 10, 12]$$$ 或 $$$a_j = 2$$$ 和 $$$a_i = [2, 4, 6, 8, 10, 12]$$$。两种情况下的 $$$v$$$ 都可以等于 $$$2$$$。
在第二个示例中,接下来的对有效:
- $$$a_j = 1$$$ 且 $$$a_i = [1, 5, 7, 11]$$$;
- $$$a_j = 2$$$ 且 $$$a_i = [1, 5, 7, 11, 10, 8, 4, 2]$$$;
- $$$a_j = 3$$$ 且 $$$a_i = [1, 3, 5, 7, 9, 11]$$$;
- $$$a_j = 6$$$ 和 $$$a_i = [1, 3, 5, 7, 9, 11, 12, 10, 8, 6, 4, 2]$$$。