Самат, герой вселенной, где обитают духи, столкнулся со сложной миссией — победить злого духа, терроризирующего этот мир уже более трёхсот лет. Самат почти одержал победу, но в последний момент злой дух применил свой коронный приём: бросок n десятигранных костей.
Этот бросок увеличивает характеристики духа. Характеристики духа увеличиваются на количество непрерывных отрезков костей $$$[l; r]$$$, где наибольший общий делитель элементов массива с позиции $$$l$$$ по $$$r$$$ — НОД$$$(a_l,a_{l+1},...,a_{r-1},a_r)$$$ равен 1, а сумма крайних элементов $$$a_l + a_r = k$$$.
Операция НОД$$$(b_1,b_2,...,b_k)$$$ примененная к $$$k$$$ числам вычисляется как последовательное вычисление наибольшего общего делителя элементов массива $$$b$$$. Например:
Теперь дух стал сильнее, и Самат хочет узнать, нужно ли вызывать помощь. Ему известны числа, выпавшие на костях. Самат передал вам результат бросков в виде массива $$$a$$$ длины $$$n$$$ и просит вас посчитать, насколько усилился дух.
В первой строке ввода даны 2 целых числа $$$n$$$ $$$(1 \le n \le 10^5)$$$ и $$$k$$$ $$$(2 \le k \le 20)$$$ — количество игровых костей и параметр $$$k$$$.
Во второй строке ввода даны $$$n$$$ чисел $$$a_1,a_2,...,a_n$$$ $$$(1 \le a_i \le 10)$$$ — числа, выпавшие на игровых костях.
Выведите ответ на задачу.
Баллы за каждую подзадачу начисляются только в случае, если все тесты и необходимые подгруппы для этой подзадачи успешно пройдены.
| Подзадача | Дополнительные ограничения | Баллы | Необходимые подгруппы | ||
| $$$n$$$ | $$$k$$$ | $$$a_i$$$ | |||
| $$$1$$$ | $$$n \le 100$$$ | — | — | $$$6$$$ | — |
| $$$2$$$ | $$$n \le 1000$$$ | $$$k \le 4$$$ | $$$a_i \le 2$$$ | $$$13$$$ | — |
| $$$3$$$ | $$$n \le 1000$$$ | — | — | $$$27$$$ | $$$1$$$, $$$2$$$ |
| $$$4$$$ | — | $$$k \le 4$$$ | $$$a_i \le 2$$$ | $$$19$$$ | $$$2$$$ |
| $$$5$$$ | — | — | — | $$$35$$$ | $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$ |
4 105 6 5 4
2
5 31 2 1 2 1
6
Давайте разберем первый пример:
