НОД против XOR
Оптимизация - это весело! Тем более, когда это совсем не обязательно.
Всем известно, что битовые операции (например, побитовое исключающее ИЛИ) выполняются быстрее, чем рекурсивные функции (такие как наибольший общий делитель, НОД). Чтобы произвести впечатление на руководителей стажировок, вы заменили в флагманском проекте компании все экземпляры gcd(x, y) гораздо более быстрыми xor(x, у).
Это было вчера, в пятницу. Теперь Вы начинаете думать, стоило ли вам тестировать новый код раньшеразвертывания в рабочей среде... Что ж, лучше поздно, чем никогда. В заданной последовательности чисел a[1], ..., a[n] определите, сколько пар (i, j) (1 ≤ i < j ≤ n) удовлетворяют равенству gcd(a[i], a[j]) = xor(a[i], a[j]) . Напомним, что gcd(x, y) - наибольший общий делитель x и y, а xor(x , y) - операция побитового исключающего ИЛИ x и y.
Входные данные
Первая строка содержит количество тестов z (1 ≤ z ≤ 20). Далее следуют описания тестов.
Первая строка каждого теста содержит целое число n (1 ≤ n ≤ 2 000 000). Вторая строка содержит целые числа a[1], a[2], ..., a[n], все положительные и не превосходящие 10^6.
Суммарная длина всех последовательностей по всем тестам не превышает 3 * 10^7.
Выходные данные
Для каждого набора входных данных выведите одно целое число: количество пар (a[i], a[j]) таких что i < j, удовлетворяющих gcd(a[ i], a[j]) = xor(a[i], a[j]).