Cho dãy số ~a~ độ dài ~n~.

Đếm số cặp ~(i, j)~ (~i \neq j~, ~1 \leq i, j \leq n~) sao cho tổng OR của ~a_i~ và ~a_j~ bằng tổng OR của ~n - 2~ số còn lại.

Hai cặp ~(i_1, j_1)~ và ~(i_2, j_2)~ được coi là khác nhau khi ~i_1 \neq i_2~ hoặc ~j_1 \neq j_2~.

Bạn có thể tìm hiểu về phép toán OR ở đây.

Input

Dòng đầu tiên là số nguyên ~n~ (~3 \leq n \leq 10^6~) là độ dài dãy ~a~.

Dòng tiếp theo gồm n số nguyên ~a_1, a_2, ..., a_n~ (~1 \leq a_i < 2^{20}~).

Output

In ra số lượng cặp ~(i, j)~ thỏa mãn.

Scoring

Sample Input 1

6
1 2 3 10 9 8

Sample Output 1

12

Notes

Có 12 cặp ~(i, j)~ thỏa mãn là:

~(1, 4)~, ~(4, 1)~, ~(2, 5)~, ~(5, 2)~, ~(3, 4)~, ~(4, 3)~, ~(3, 5)~, ~(5, 3)~, ~(3, 6)~, ~(6, 3)~, ~(4, 5)~, ~(5, 4)~.

Xét cặp ~(1, 4)~:

— ~a_1~ OR ~a_4~ = ~1~ OR ~10~ = ~11~.

— ~a_2~ OR ~a_3~ OR ~a_5~ OR ~a_6~ = ~2~ OR ~3~ OR ~9~ OR ~8~ = ~11~.

Vì tổng OR của ~a_1~ và ~a_4~ bằng tổng OR của các số còn lại nên cặp ~(1, 4)~ là một cặp thỏa mãn.