У Васи есть последовательность, состоящая из n целых чисел. Вася считает пару чисел x и y k-интересной, если их двоичное представление отличается друг от друга ровно в k битах. Например, если k = 2, то пара чисел x = 5 и y = 3 является k-интересной, так как двоичные представления x=101 и y=011 отличаются ровно в двух битах.
Васе стало интересно, сколько в его последовательности существует пар индексов (i, j) таких, что i < j и пара чисел ai и aj является k-интересной. Перед вами стоит задача помочь Васе и определить это количество.
Выходные данные
Выведите количество пар (i, j) таких, что i < j и пара чисел ai и aj является k-интересной.
Примечание
В первом примере существует 4 k-интересные пары:
- (1, 3),
- (1, 4),
- (2, 3),
- (2, 4).
Во втором примере k = 0. Следовательно, числа в любой k-интересной паре должны быть равны между собой. Таким образом, для второго примера существует 6 k-интересных пар:
- (1, 5),
- (1, 6),
- (2, 3),
- (2, 4),
- (3, 4),
- (5, 6).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 1
0 3 2 1
|
4
|
|
2
|
6 0
200 100 100 100 200 200
|
6
|