Vova 再次尝试玩一些电脑纸牌游戏。
这个游戏中的套牌创建规则很简单。给 Vova 一副现有的 n 张牌和一个幻数 k。牌组中的牌的顺序是固定的。每张卡片上都写有一个数字;数字ai写在这副牌中的第i张卡上。
在收到这副牌和魔法数字后,Vova从牌堆顶部移除x(可能x = 0)张牌,从牌堆底部移除y(可能y = 0)张牌,剩下的牌组就是他的新牌组(移除牌后Vova必须在牌堆中至少留下一张牌)。因此,Vova 的新牌组实际上包含原始牌组中的牌 x + 1、x + 2、... n - y - 1、n - y。
Vova 的新牌组被认为是有效的,当且仅当其新牌组中的牌上写的所有数字的乘积能被 k 整除。因此,Vova 收到了一副牌(可能不是有效牌)和一个数字 k,现在他想知道,有多少种方法可以选择 x 和 y,以便从顶部移走 x 张牌和从底部移走 y 张牌后,他得到的牌堆是有效的?
输入
第一行包含两个整数 n 和 k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 109)。
第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109) — 写在卡片上的数字。
输出
打印选择 x 和 y 的方法数,以便生成的牌组有效。
示例
输入 #1
3 4 6 2 8
输出 #1
4
输入 #2
3 6 9 1 14
输出 #2
1
注意
在第一个示例中,x 和 y 的可能值为:
1. x = 0, y = 0;
2. x = 1, y = 0;
3. x = 2, y = 0;
4. x = 0, y = 1。