Basme

Xorin se plimba pe stradă când a dat peste un șir $u$ de $N$ numere naturale. Curios din fire, acesta vrea să aplice operații alchimice fiecărui element din șir. Singura operație alchimică știută de el este "solve et coagula" (dizolvă și coagulează), învățată dintr-un eseu despre Harap Alb. Procedeul "solve et coagula" este următorul: se ia un număr natural, de exemplu $84$, se descompune în factori primi ($84 = 2^2 \cdot 3 \cdot 7$), iar rezultatul se obține din suma xor a acestor factori primi, luați o singură dată ($2 \oplus 3 \oplus 7 = 6$).

Xorin aplică procedeul "solve et coagula" fiecărui element din șirul $u$, obținând un nou șir $v$ (elementului $u_i$ îi corespunde elementul $v_i$).

Cerință

Roxana găsește noul șir $v$ și vă adresează o întrebare: câte perechi de indici $(a, b)$, unde $1 \leq a \leq b \leq N$, există, cu proprietatea că suma xor a elementelor $v_i$, cu $a \leq i \leq b$, este $0$?

Date de intrare

Prima linie conține numărul natural $N$. A doua linie conține $N$ numere naturale, elementele șirului inițial $u$.

Date de ieșire

Fișierul de ieșire va conține pe prima linie numărul de perechi de indici $( a, b )$, cu proprietatea specificată anterior.

Restricții și precizări

• $1 \leq N \leq 200 \ 000$
• $2 \leq u_i \leq V$, oricare ar fi $1 \leq i \leq N$.
• $1 \leq V \leq 10 \ 000 \ 000$
• Aplicarea procedeului pentru valoarea $1$ va da ca rezultat $0$.
• Pentru teste în valoare de $21$ puncte, $N \leq 1 \ 000$ și $V \leq 1 \ 000 \ 000$.
• Pentru teste în valoare de $39$ de puncte, $N \leq 40 \ 000$ și $V \leq 10 \ 000 \ 000$.
• Pentru teste în valoare de $17$ puncte, $N \leq 200 \ 000$ și $V \leq 10 \ 000 \ 000$ și toate numerele sunt prime.
• Pentru teste în valoare de $23$ de puncte, nu există restricții suplimentare.
• Operaţia xor reprezintă operaţia de disjuncţie exclusivă. Tabelul de mai jos reprezintă tabelul acestei operatii, pentru 2 biţi.
• În cazul acestei probleme, operaţia xor se realizează pe biţii operanzilor. De exemplu, $5 \oplus 12 = 9$ ($0101_2 \oplus 1100_2 = 1001_2$).
• Prin suma xor a $n$ numere $x_i$, se înțelege rezultatul obținut prin aplicarea succesivă a operației xor între acestea: $x_1 \oplus x_2 \oplus \dots \oplus x_{n−1} \oplus x_n$.
• În C/C++, operatorul pentru xor este ^, iar în Pascal, operatorul corespunzător este xor.

Exemplul 1

basme.in

3
236 23 410

basme.out

1

Explicație

$u_1 = 236$ are factorii primi $2$ și $59$, deci $v_1 = 2 \oplus 59 = 57$. $u_2 = 23$ este prim, deci $v_2 = 23$. $u_3 = 410 = 41 \cdot 2 \cdot 5$, deci $v_3 = 41 \oplus 2 \oplus 5 = 46$. Astfel, șirul $v$ este $[57, 23, 46]$. Singura subsecvență continuă care are suma xor $0$ este $[57, 23, 46]$, deci răspunsul este $1$.

Exemplul 2

basme.in

10
84 4 5 6 10 225 2 13 15 26

basme.out

3

Explicație

Șirul inițial $u$ se transformă în următorul șir $v$: $[6, 2, 5, 1, 7, 6, 2, 13, 6, 15]$. Subsecvențele $[6, 2, 5, 1]$, $[ 5, 1, 7, 6 ]$ și $[7, 6, 2, 13, 6, 15]$ au suma xor $0$. Astfel, pentru acest șir, sunt $3$ perechi de indici care respectă proprietatea cerută: $(1, 4)$, $(3, 6)$ și $(5, 10)$.