Bessie and Elsie are playing a game with N (1≤N≤105) piles of stones, where the i-th pile has a_istones for each 1≤i≤N(1≤a_i≤106). The two cows alternate turns, with Bessie going first.

First, Bessie chooses some positive integer s_1 and removes s_1 stones from some pile with at least s_1 stones.

Then Elsie chooses some positive integer s_2 such that s_1 divides s_2 and removes s_2 stones from some pile with at least s_2stones.

Then Bessie chooses some positive integer s_3 such that s_2 divides s_3 and removes s_3 stones from some pile with at least s_3

stones and so on.

In general, s_i, the number of stones removed on turn i, must divide s_i+1.

The first cow who is unable to remove stones on her turn loses.

Compute the number of ways Bessie can remove stones on her first turn in order to guarantee a win (meaning that there exists a strategy such that Bessie wins regardless of what choices Elsie makes). Two ways of removing stones are considered to be different if they remove a different number of stones or they remove stones from different piles.

#5774 upload - done - how_to_reg -

Stone Game timer 1s memory 512MB

#5774

Stone Game 1s 512MB