Оптимизация — это весело! Особенно когда она не совсем обязательна.

Все знают, что побитовые операции (например, побитовое исключающее ИЛИ, XOR) быстрее, чем рекурсивные функции (такие как наибольший общий делитель, НОД). Чтобы впечатлить своих руководителей на стажировке, вы заменили в флагманском проекте компании все вызовы $gcd(x, y)$ на гораздо более быстрые $xor(x, y)$.

Это было вчера, в пятницу. Теперь вы начинаете задумываться, стоило ли тестировать ваш новый код перед внедрением в производство... Что ж, лучше поздно, чем никогда. Дана последовательность чисел $a_1, \dots, a_n$. Определите, сколько пар $(i, j)$ ($1 \le i < j \le n$) на самом деле удовлетворяют условию $gcd(a_i, a_j) = xor(a_i, a_j)$. Напомним, что $gcd(x, y)$ обозначает наибольший общий делитель $x$ и $y$, а $xor(x, y)$ — это операция побитового исключающего ИЛИ над $x$ и $y$.

Входные данные

Первая строка входных данных содержит количество тестов $z$ ($1 \le z \le 20$). Далее следуют описания тестов.

Первая строка каждого теста содержит целое число $n$ ($1 \le n \le 2\,000\,000$). Вторая строка содержит целые числа $a_1, a_2, \dots, a_n$, все они положительные и не превышают $1\,000\,000$.

Суммарная длина всех последовательностей во всех тестах не превышает $3 \cdot 10^7$.

Выходные данные

Для каждого теста выведите одно целое число: количество пар $(i, j)$ таких, что $i < j$ и $gcd(a_i, a_j) = xor(a_i, a_j)$.

Примеры

Входные данные 1

1
4
2 3 4 3

Выходные данные 1

2