Новый год совсем близко, а это значит, что в 179-й школе уже полным ходом идет подготовка к новогоднему концерту.

Всего в школе есть $$$n$$$ классов, пронумерованных целыми числами от $$$1$$$ до $$$n$$$, $$$i$$$-й класс подготовил сценку продолжительностью $$$a_i$$$ минут.

Иднар, как главный за проведение новогоднего концерта, знает, что если на концерте будет $$$k$$$ сценок продолжительностями $$$b_1$$$, $$$b_2$$$, $$$\ldots$$$, $$$b_k$$$ минут, то зрителям станет скучно, если найдутся $$$l$$$ и $$$r$$$ такие, что $$$1 \le l \le r \le k$$$ и $$$\gcd(b_l, b_{l + 1}, \ldots, b_{r - 1}, b_r) = r - l + 1$$$, где $$$\gcd(b_l, b_{l + 1}, \ldots, b_{r - 1}, b_r)$$$ обозначает наибольший общий делитель (НОД) чисел $$$b_l$$$, $$$b_{l + 1}$$$, $$$\ldots$$$, $$$b_{r - 1}$$$, $$$b_r$$$.

Чтобы во время концерта зрителям не стало скучно, Иднар может сколько угодно раз (возможно, ноль) попросить $$$t$$$-й класс ($$$1 \le t \le k$$$) сделать другую сценку продолжительностью $$$d$$$, где $$$d$$$ может быть любым целым положительным числом. Таким образом, после данной операции $$$b_t$$$ станет равно $$$d$$$. Заметьте, что $$$t$$$ и $$$d$$$ для разных операций могут быть различными.

Для последовательности продолжительностей сценок $$$b_1$$$, $$$b_2$$$, $$$\ldots$$$, $$$b_{k}$$$ определим функцию $$$f(b)$$$ как минимальное количество классов, у которых Иднар должен попросить заменить сценку, чтобы зрителям не стало скучно.

Иднар еще точно не определился, какие сценки будут допущены на концерт, поэтому хочет узнать значение функции $$$f$$$ от каждого из непустых префиксов $$$a$$$. Иными словами, Иднар хочет узнать значения $$$f(a_1)$$$, $$$f(a_1$$$,$$$a_2)$$$, $$$\ldots$$$, $$$f(a_1$$$,$$$a_2$$$,$$$\ldots$$$,$$$a_n)$$$.