题目描述

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

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

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

\[ f\left(\prod_{i=l}^{r} a_i\right) = f(X) \]

输入格式

输入共两行。第一行包含两个正整数 \(N\) 和 \(X\)，分别表示材料序列的长度和目标样本的能量值。第二行包含 \(N\) 个正整数 \(a_1,a_2,\dots,a_N\)，表示序列 \(A\) 中每瓶材料的能量值，整数之间用空格分隔。数据范围： \(2 \le N \le 5\times 10^5\)，\(1 \le a_i \le 10^6\)，\(1 \le X \le 10^6\)（补充说明 \(f(1)=1\)）。

输出格式

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

样例输入

5 6
2 3 6 12 1

样例输出

4