Беси и Эльза играют в игру с n кучками камушков, где i-ая (1 ≤ i ≤ n) кучка содержит ai камешков (1 ≤ ai ≤ 106). Они ходят по очереди, первой ходит Беси.

• Сначала Беси выбирает некоторое положительное число s1 и удаляет s1 камешков из некоторой кучки, в которой есть не менее s1 камешков
• Затем Эльза выбирает некоторое положительное число s2 такое, что s2 делится на s1 и удаляет s2 камешков из некоторой кучки, содержащей не менее s2 камешков.
• Затем Беси выбирает некоторое положительное число s3, которое делится на s2 и удаляет s3 камешков из некоторой кучки, в которой есть не менее s3 камешков
• В общем случае si, количество камешков, которое убирается на ходу i, должно быть делителем si+1.

Проигрывает первая корова, которая не может сделать ход.

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

Входные данные

Первая строка содержит n (1 ≤ n ≤ 105).

Вторая строка содержит n целых чисел a1,..., an.

Выходные данные

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

Для вычислений используйте 64-ное целое например, "long long" в C/C++.

Пример 1

Беси выиграет 4, 5, 6, 7 камушков из одной кучи и игра закончится сразу.

Пример 2

Беси выиграет, если удалит 2 или 3 камушка из любой кучи. Затем игроки будут по очереди брать одно и то же количество камушков, но Беси сделает последний ход.