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

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

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

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

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

【数据范围】

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

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

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