Source : 中山纪念中学宋新波老师
Description

给定一个长度为n的序列a以及常数k,序列从1开始编号。

,求合法的正整数对(l,r)的数量,满足1<=l<r<=n,且k|f(l,r).

Input

第一行两个正整数n和k。

第二行包含n个正整数,第i个正整数表示ai。

Output

一行一个正整数,表示答案。

Sample Input 1
4 3
1 2 3 4
Sample Output 1
3
Sample Input 2
4 2
4 4 7 4
Sample Output 2
6
Hint

【数据范围】

对于30%的数据,n<=3000;

对于另外20%的数据,数列a为随机生成;

对于100%的数据,1<=n<=3*10^5,1<=k<=10^6,1<=ai<=10^9。