题目描述

炼金术士小 A 正在尝试提炼一种传说中的“贤者之石”。根据古老的炼金术手稿记载，提炼过程需要达成一种特定的“元素共鸣”。 小 A 的实验台上摆放着一排由 $N$ 瓶炼金材料组成的序列，序列记为 $A$，其中第 $i$ 瓶材料的能量值为 $a[i]$。此外，他还有一个作为参考标准的“目标样本”，其能量值为 $X$。 为了定义共鸣，我们引入物质的“核心本质”概念。对于任意正整数 $v$，其“核心本质” $f{(v)}$ 的定义如下： 将 $v$ 进行标准质因数分解 $v = p_1^{k_1} \times p_2^{k_2} \times ... \times p_m^{k_m}$，则 $f(v)$ 等于所有指数 $k_i$ 为奇数的质因数 $p_i$ 的乘积。 例如：

• 对于数字 $12$，分解为 $2^2 * 3^1$，指数为奇数的质因数是 $3$，故 $f(12) = 3$。
• 对于数字 $90$，分解为 $2^1 * 3^2 * 5^1$，指数为奇数的质因数是 $2$ 和 $5$，故 $f(90) = 10$。
• 对于数字 $36$，分解为 $2^2 * 3^2$，没有指数为奇数的质因数，故 $f(36) = 1$。
• 对于数字 $27$，分解为 $3^3$， 唯一质因数 $3$ 的指数是奇数，故 $f(27) = 3$。

小 A 需要在原材料序列 $A$ 中找到一个连续子区间 $[l, r]$，使得该子区间内所有材料能量值的乘积，其“核心本质”与目标样本 $X$ 的“核心本质”完全相同。 请你计算，有多少对下标 ($l$,$r$) 满足 ($1 \leq l \leq r \leq N$) 满足以下条件：

输入格式

输入共两行。

第一行包含两个正整数 $N$ 和 $X$，分别表示材料序列的长度和目标样本的能量值。

第二行包含 $N$ 个正整数 $a[1],a[2],...,a[n]$，表示序列 $A$ 中每瓶材料的能量值，整数之间用空格分隔。（补充说明 $f(1)=1$ )

输出格式

输出一个整数，表示满足条件的连续子区间 $[l, r]$ 的总数量。

5 6
2 3 6 12 1

4

数据范围

$2 \leq N \leq 5 * 10^5 , 1 \leq a[i] \leq 10^6 , 1 \leq X \leq 10^6$