Бесі та Ельза грають у гру з \(N\) (\(1\le N\le 10^5\)) купками камінчиків, де \(i\)-а купка містить \(a_i\) камінців \(1\le i\le N\) (\(1\le a_i\le 10^6\)). Вони ходять по черзі, першою ходить Бесі.

• Спочатку Бесі вибирає деяке додатне число \(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\).

Другий рядок містить \(N\) розділених одиночними пробілами цілих чисел \(a_1,\ldots,a_N\).

Формат вихідних даних

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

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

Приклад вхідних даних

1
7

Приклад вихідних даних

4

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

Приклад вхідних даних

6
3 2 3 2 3 1

Приклад вихідних даних

8

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

ОЦІНЮВАННЯ:

• У тестах 1-5 \(N=2\).
• У тестах 6-10 \(N,a_i\le 100\).
• У тестах 11-20 немає додаткових обмежень.