돌 게임

Bessie와 Elsie가 $N$ ($1\le N\le 10^5$)개의 돌 더미로 게임을 한다. $i$번째 더미에는 $a_i$개의 돌이 있다 ($1\le i\le N$, $1\le a_i\le 10^6$). 두 소가 번갈아 차례를 가지며, Bessie가 먼저 시작한다.

• 먼저 Bessie가 양의 정수 $s_1$을 골라 돌이 $s_1$개 이상 있는 더미에서 돌 $s_1$개를 가져간다.
• 그다음 Elsie가 $s_1$이 $s_2$를 나누는 양의 정수 $s_2$를 골라 돌이 $s_2$개 이상 있는 더미에서 돌 $s_2$개를 가져간다.
• 그다음 Bessie가 $s_2$가 $s_3$을 나누는 양의 정수 $s_3$을 골라 돌이 $s_3$개 이상 있는 더미에서 돌 $s_3$개를 가져가고, 이런 식으로 이어진다.
• 일반적으로 $i$번째 차례에 가져가는 돌의 개수 $s_i$는 $s_{i+1}$을 나누어야 한다.

자기 차례에 돌을 가져가지 못하는 소가 진다.

Bessie가 승리를 보장받기 위해(Elsie가 어떤 선택을 하더라도 Bessie가 이기는 전략이 존재한다는 뜻이다) 첫 차례에 돌을 가져가는 방법의 수를 구하여라. 가져가는 돌의 개수가 다르거나 돌을 가져가는 더미가 다르면 서로 다른 방법으로 본다.

첫째 줄에 $N$이 주어진다.

둘째 줄에 $N$개의 정수 $a_1,\ldots,a_N$이 공백으로 구분되어 주어진다.

Bessie가 승리를 보장받기 위해 첫 차례에 돌을 가져가는 방법의 수를 출력한다.

이 문제에서 다루는 정수의 크기가 크므로 64비트 정수 자료형(예: C/C++의 "long long")이 필요할 수 있다.