Bessie và Elsie chơi một trò chơi với \(N\) đống đá (\(1\le N\le10^5\)), trong đó đống thứ \(i\) có \(a_i\) viên với mọi \(1\le i\le N\) (\(1\le a_i\le10^6\)). Hai cô bò luân phiên lượt chơi và Bessie đi trước.

Đầu tiên, Bessie chọn một số nguyên dương \(s_1\) và lấy \(s_1\) viên khỏi một đống có ít nhất \(s_1\) viên. Sau đó, Elsie chọn một số nguyên dương \(s_2\) sao cho \(s_2\) chia hết cho \(s_1\), rồi lấy \(s_2\) viên khỏi một đống có ít nhất \(s_2\) viên. Tiếp theo, Bessie chọn số nguyên dương \(s_3\) sao cho \(s_3\) chia hết cho \(s_2\) và lấy \(s_3\) viên khỏi một đống có ít nhất \(s_3\) viên, và cứ thế tiếp tục.

Nói chung, số đá \(s_i\) được lấy ở lượt \(i\) phải là ước của \(s_{i+1}\). Người đầu tiên không thể lấy đá trong lượt của mình sẽ thua.

Hãy tính số cách Bessie có thể lấy đá trong lượt đầu để bảo đảm chiến thắng, nghĩa là tồn tại một chiến lược giúp Bessie thắng bất kể Elsie lựa chọn thế nào. Hai cách được coi là khác nhau nếu lấy số viên đá khác nhau hoặc lấy từ các đống khác nhau.

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

Dòng thứ hai chứa \(N\) số nguyên \(a_1,\ldots,a_N\), cách nhau bởi dấu cách.

Dữ liệu ra

In số cách Bessie có thể lấy đá trong lượt đầu để bảo đảm chiến thắng. Kết quả có thể cần kiểu số nguyên 64 bit, chẳng hạn long long trong C/C++.

Phân nhóm

• Các test 3-5 thỏa mãn \(N=2\).
• Các test 6-10 thỏa mãn \(N,a_i\le100\).
• Các test 11-20 không có ràng buộc bổ sung.

Ví dụ

1
7

4

6
3 2 3 2 3 1

8

Nguồn

USACO 2021 February Contest, Gold - Stone Game: https://usaco.org/index.php?page=viewproblem2&cpid=1113

Tác giả: Benjamin Qi.