Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

G. Appropriate Team

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputSince next season are coming, you'd like to form a team from two or three participants. There are $$$n$$$ candidates, the $$$i$$$-th candidate has rank $$$a_i$$$. But you have weird requirements for your teammates: if you have rank $$$v$$$ and have chosen the $$$i$$$-th and $$$j$$$-th candidate, then $$$GCD(v, a_i) = X$$$ and $$$LCM(v, a_j) = Y$$$ must be met.

You are very experienced, so you can change your rank to any non-negative integer but $$$X$$$ and $$$Y$$$ are tied with your birthdate, so they are fixed.

Now you want to know, how many are there pairs $$$(i, j)$$$ such that there exists an integer $$$v$$$ meeting the following constraints: $$$GCD(v, a_i) = X$$$ and $$$LCM(v, a_j) = Y$$$. It's possible that $$$i = j$$$ and you form a team of two.

$$$GCD$$$ is the greatest common divisor of two number, $$$LCM$$$ — the least common multiple.

Input

First line contains three integers $$$n$$$, $$$X$$$ and $$$Y$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le X \le Y \le 10^{18}$$$) — the number of candidates and corresponding constants.

Second line contains $$$n$$$ space separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{18}$$$) — ranks of candidates.

Output

Print the only integer — the number of pairs $$$(i, j)$$$ such that there exists an integer $$$v$$$ meeting the following constraints: $$$GCD(v, a_i) = X$$$ and $$$LCM(v, a_j) = Y$$$. It's possible that $$$i = j$$$.

Examples

Input

12 2 2

1 2 3 4 5 6 7 8 9 10 11 12

Output

12

Input

12 1 6

1 3 5 7 9 11 12 10 8 6 4 2

Output

30

Note

In the first example next pairs are valid: $$$a_j = 1$$$ and $$$a_i = [2, 4, 6, 8, 10, 12]$$$ or $$$a_j = 2$$$ and $$$a_i = [2, 4, 6, 8, 10, 12]$$$. The $$$v$$$ in both cases can be equal to $$$2$$$.

In the second example next pairs are valid:

- $$$a_j = 1$$$ and $$$a_i = [1, 5, 7, 11]$$$;
- $$$a_j = 2$$$ and $$$a_i = [1, 5, 7, 11, 10, 8, 4, 2]$$$;
- $$$a_j = 3$$$ and $$$a_i = [1, 3, 5, 7, 9, 11]$$$;
- $$$a_j = 6$$$ and $$$a_i = [1, 3, 5, 7, 9, 11, 12, 10, 8, 6, 4, 2]$$$.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/11/2018 22:18:43 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|