小红和小紫的取数游戏

题目描述

小红和小紫进行一个取数游戏。游戏的规则是：初始一个数$x$，小红先手，双方轮流取$x$的一个因子$p$，要求$p$不能被除了 1 以外的任意完全平方数整除。谁先将$x$取到 1 谁赢。
由于小红是先手，小紫觉得这个游戏对小红的优势太大了，于是她提出了一个解决方案：给定了一个数组$a$，在游戏开始前，小紫可以选择该数组的一个连续子数组$[a_l,a_{l+1},...,a_r]$，使得$x$乘上这个连续子数组的每个元素，然后再开始游戏。
小紫想知道，有多少种选择方式可以使得自己立于不败之地？

输入格式

第一行输入两个正整数$n,x$，代表给定的数组大小、游戏的初始数字$x$。
第二行输入$n$个正整数$a_i$，代表给定的数组。
$1\leq n,a_i \leq 10^5$
$1\leq x \leq 10^{12}$

输出格式

一个正整数，代表小紫可选的区间方案数。

样例 #1

样例输入 #1

5 2
1 2 3 6 12

样例输出 #1

4

提示

选择[2]、[1,2]、[3,6]或[6,12]区间均可。