Недавно K1o0n импульсивной покупкой взял $$$n$$$ упаковок чая и теперь думает, когда же успеет перепробовать все купажи. В чае он привередлив, поэтому каждой упаковке сразу выставил насыщенность — целое число $$$a_i$$$.

Упаковки стоят на полке в порядке покупки, и разбирать их K1o0n ленится: заваривая, он ссыпает в чайник подряд первые $$$j$$$ упаковок, а потом добавляет ещё одну ложку из упаковки с номером $$$i$$$. Получившийся купаж обозначим $$$(i, j)$$$, а его насыщенностью назовём произведение насыщенностей всего, что в него попало:

$$$$$$F(i, j) = a_i \cdot \prod_{k=1}^{j} a_k = a_i \cdot \left(a_1 \cdot a_2 \cdot \ldots \cdot a_j\right)$$$$$$

Готовый чайник K1o0n разливает по одинаковым чашкам: на $$$d$$$ чашек он разольёт его тогда и только тогда, когда $$$d$$$ — натуральный делитель числа $$$F(i, j)$$$, и каждой чашке достанется поровну. Купаж он называет капризным, если число подходящих $$$d$$$ нечётно.

Посчитайте, сколько капризных купажей может заварить K1o0n, то есть сколько пар $$$(i, j)$$$ с $$$1 \le i \le n$$$ и $$$1 \le j \le n$$$ дают нечётное количество натуральных делителей числа $$$F(i, j)$$$.