Гра з камінням

Бесі та Ельза грають у гру з n купками камінців, де i-та (1 ≤ i ≤ n) купка містить a[i] камінців (1 ≤ a[i] ≤ 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], кількість камінців, що видаляється на ході i, має бути дільником s[i+1].

Програє перша корова, яка не може зробити хід.

Обчисліть кількість способів, якими Бесі може видалити камінці на першому ході для того, щоб гарантувати собі перемогу (тобто існує стратегія, використовуючи яку Бесі переможе незалежно від ходів Ельзи). Два способи видалення камінців називаються різними, якщо вони видаляють різну кількість камінців або вони видаляють камінці з різних купок.

Вхідні дані

Перша рядок містить n (1 ≤ n ≤ 10^5).

Друга рядок містить n цілих чисел a[1],..., a[n].

Вихідні дані

Виведіть кількість способів, якими Бесі може видалити камінці на першому ході, щоб гарантувати собі виграш.

Для обчислень використовуйте 64-бітне ціле, наприклад, "long long" у C/C++.

Приклад 1

Бесі виграє, якщо видалить 4, 5, 6, 7 камінців з однієї купки і гра закінчиться одразу.

Приклад 2

Бесі виграє, якщо видалить 2 або 3 камінці з будь-якої купки. Потім гравці будуть по черзі брати одну і ту ж кількість камінців, але Бесі зробить останній хід.

Приклади