Tối ưu hóa thật thú vị! Đặc biệt là khi nó không thực sự cần thiết.

Ai cũng biết rằng các phép toán bit (ví dụ: XOR bit) nhanh hơn các hàm đệ quy (như ước chung lớn nhất, GCD). Để gây ấn tượng với người giám sát thực tập, bạn đã thay thế tất cả các trường hợp $gcd(x, y)$ trong dự án chủ chốt của công ty bằng $xor(x, y)$ nhanh hơn nhiều.

Đó là chuyện của ngày hôm qua, thứ Sáu. Bây giờ bạn bắt đầu suy nghĩ liệu mình có nên kiểm tra mã nguồn mới trước khi đưa vào vận hành thực tế hay không... Chà, muộn còn hơn không. Cho một dãy số $a_1, \dots, a_n$, hãy xác định có bao nhiêu cặp $(i, j)$ ($1 \le i < j \le n$) thực sự thỏa mãn $gcd(a_i, a_j) = xor(a_i, a_j)$. Nhắc lại rằng $gcd(x, y)$ biểu thị ước chung lớn nhất của $x$ và $y$, trong khi $xor(x, y)$ là phép toán XOR bit giữa $x$ và $y$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa số lượng bộ test $z$ ($1 \le z \le 20$). Các mô tả của các bộ test theo sau.

Dòng đầu tiên của một bộ test chứa một số nguyên $n$ ($1 \le n \le 2\,000\,000$). Dòng thứ hai chứa các số nguyên $a_1, a_2, \dots, a_n$, tất cả đều là số dương và không vượt quá $1\,000\,000$.

Tổng độ dài của tất cả các dãy số qua tất cả các bộ test không vượt quá $3 \cdot 10^7$.

Dữ liệu ra

Với mỗi bộ test, hãy in ra một số nguyên duy nhất: số lượng cặp $(i, j)$ với $i < j$ thỏa mãn $gcd(a_i, a_j) = xor(a_i, a_j)$.

Ví dụ

Dữ liệu vào 1

1
4
2 3 4 3

Dữ liệu ra 1

2