Гра з камінням#11213
Бесі та Ельза грають у гру з купками камінців, де -та (1 \leq i \leq n) купка містить a_i (1 \leq a_i \leq 10^6) камінців. Вони ходять по черзі, першою ходить Бесі.
Спочатку Бесі обирає деяке додатне число s_1 і видаляє s_1 камінців з деякої купки, в якій є не менше s_1 камінців.
Потім Ельза обирає деяке додатне число s_2 таке, що s_2 ділиться на s_1 і видаляє s_2 камінців з деякої купки, що містить не менше s_2 камінців.
Потім Бесі обирає деяке додатне число s_3, яке ділиться на s_2 і видаляє s_3 камінців з деякої купки, в якій є не менше s_3 камінців.
У загальному випадку s_i, кількість камінців, що видаляється на ході , має бути дільником s_{i+1}.
Програє перша корова, яка не може зробити хід.
Обчисліть кількість способів, якими Бесі може видалити камінці на першому ході для того, щоб гарантувати собі перемогу (тобто існує стратегія, використовуючи яку Бесі переможе незалежно від ходів Ельзи). Два способи видалення камінців називаються різними, якщо вони видаляють різну кількість камінців або вони видаляють камінці з різних купок.
Перший рядок містить (1 \leq n \leq 10^5).
Другий рядок містить цілих чисел a_1, \ldots, a_n.
Виведіть кількість способів, якими Бесі може видалити камінці на першому ході, щоб гарантувати собі виграш.
Для обчислень використовуйте 64-бітне ціле, наприклад, "long long" у C/C++.
\Example 1
Бесі виграє, якщо видалить , , , камінців з однієї купки і гра закінчиться одразу.
\Example 2
Бесі виграє, якщо видалить або камінці з будь-якої купки. Потім гравці будуть по черзі брати одну і ту ж кількість камінців, але Бесі зробить останній хід.
Приклад 1
Приклад 2