НОД проти XOR
Оптимізація - це весело! Особливо, коли вона зовсім не обов'язкова.
Відомо, що бітові операції, такі як побітове виключне АБО, виконуються швидше, ніж рекурсивні функції, наприклад, обчислення найбільшого спільного дільника (НСД). Щоб вразити керівників стажувань, ви вирішили замінити у флагманському проєкті компанії всі виклики gcd(x, y) на значно швидші xor(x, y).
Це сталося вчора, у п'ятницю. Тепер ви починаєте замислюватися, чи не варто було протестувати новий код перед його розгортанням у робочому середовищі... Що ж, краще пізно, ніж ніколи. У заданій послідовності чисел 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]).