У Поликарпа есть два любимых числа \(x\) и \(y\) (они могут быть равны), также он нашёл массив \(a\) длины \(n\).
Поликарп считает пару индексов \(\langle i, j \rangle\) (\(1 \le i < j \le n\)) красивой, если:
- \(a_i + a_j\) делится нацело на \(x\);
- \(a_i - a_j\) нацело делится на \(y\).
Например, если \(x=5\), \(y=2\), \(n=6\), \(a=\)[\(1, 2, 7, 4, 9, 6\)], то красивыми являются только пары:
- \(\langle 1, 5 \rangle\): \(a_1 + a_5 = 1 + 9 = 10\) (\(10\) делится на \(5\)) и \(a_1 - a_5 = 1 - 9 = -8\) (\(-8\) делится на \(2\));
- \(\langle 4, 6 \rangle\): \(a_4 + a_6 = 4 + 6 = 10\) (\(10\) делится на \(5\)) и \(a_4 - a_6 = 4 - 6 = -2\) (\(-2\) делится на \(2\)).
Найдите количество
красивых пар в массиве
\(a\).
Выходные данные
Для каждого набора входных данных выведите единственное число — количество красивых пар в массиве \(a\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
6 5 2
1 2 7 4 9 6
7 9 5
1 10 15 3 8 12 15
9 4 10
14 10 2 2 11 11 13 5 6
9 5 6
10 7 6 7 9 7 7 10 10
9 6 2
4 9 7 1 2 2 13 3 15
9 2 3
14 6 1 15 12 15 8 2 15
10 5 7
13 3 3 2 12 11 3 7 13 14
|
2
0
1
3
5
7
0
|