Близится следующий сезон, поэтому Вы решили собрать команду из двух или трех человек. У Вас есть \(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\) — наименьшее общее кратное.
Выходные данные
Выведите единственное число — количество пар \((i, j)\), что существует \(v\) такой, что \(GCD(v, a_i) = X\) и \(LCM(v, a_j) = Y\). Ситуация \(i = j\) разрешена.
Примечание
В первом примере следующие пары валидны: \(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]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
12 2 2
1 2 3 4 5 6 7 8 9 10 11 12
|
12
|
|
2
|
12 1 6
1 3 5 7 9 11 12 10 8 6 4 2
|
30
|