НОД проти XOR#11107

НОД проти XOR

1 секунда

128 мегабайтів

Легка

Оптимізація - це весело! Особливо, коли вона зовсім не обов'язкова.

Відомо, що бітові операції, такі як побітове виключне АБО, виконуються швидше, ніж рекурсивні функції, наприклад, обчислення найбільшого спільного дільника (НСД). Щоб вразити керівників стажувань, ви вирішили замінити у флагманському проєкті компанії всі виклики $g cd (x, y)$ \gcd(x, y) на значно швидші $xor (x, y)$ \text{xor}(x, y).

Це сталося вчора, у п'ятницю. Тепер ви починаєте замислюватися, чи не варто було протестувати новий код перед його розгортанням у робочому середовищі... Що ж, краще пізно, ніж ніколи. У заданій послідовності чисел $a_{1}, \dots, a_{n}$ a_1, \ldots, a_n визначте, скільки пар $(i, j)$ ( $1 \leq i < j \leq n$ 1 \le i < j \le n) задовольняють рівність $g cd (a_{i}, a_{j}) = xor (a_{i}, a_{j})$ \gcd(a_i, a_j) = \text{xor}(a_i, a_j). Нагадаємо, що $g cd (x, y)$ \gcd(x, y) - це найбільший спільний дільник $x$ і $y$ , а $xor (x, y)$ \text{xor}(x, y) - це операція побітового виключного АБО $x$ і $y$ .

Вхідні дані

Перший рядок містить кількість тестів $z$ ( $1 \leq z \leq 20$ 1 \le z \le 20). Далі йдуть описи тестів.

Перший рядок кожного тесту містить ціле число $n$ ( $1 \leq n \leq 2000000$ 1 \le n \le 2\,000\,000). Другий рядок містить цілі числа $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n, всі додатні і не перевищують $1 0^{6}$ 10^6.

Сумарна довжина всіх послідовностей по всіх тестах не перевищує $3 \cdot 1 0^{7}$ 3 \cdot 10^7.

Вихідні дані

Для кожного набору вхідних даних виведіть одне ціле число: кількість пар $(a_{i}, a_{j})$ (a_i, a_j) з $i < j$ i < j, що задовольняють умову $g cd (a_{i}, a_{j}) = xor (a_{i}, a_{j})$ \gcd(a_i, a_j) = \text{xor}(a_i, a_j).

Приклади

Приклад 1