Cho hai số nguyên dương \(n,k\) và một dãy gồm \(n\) số nguyên dương \(a_1,a_2,…,a_n.\)

Yêu cầu: Tìm số lượng cặp số \((l,r)\) với \(1≤l≤r≤n\) sao cho trong các số \(a_l,a_{l+1},…,a_r\) có tối đa một số chia hết cho \(k\).

Input

• Dòng 1: chứa hai số nguyên dương \(n\) và \(k (1≤n≤3×10^5,1≤k≤10^9 );\)

• Dòng 2: chứa \(n\) số nguyên \(a_1,a_2,…,a_n (a_i ≤10^9 với 1≤i≤n). \)

Các số trên cùng một dòng được ghi cách nhau một khoảng trắng.

Output

• Một dòng duy nhất là số lượng cặp số \((l,r)\) thỏa mãn yêu cầu đề bài.

Ràng buộc:

• Subtask 1: 50% test có \(n≤2000;\)

• Subtask 2: 50% test không có ràng buộc gì thêm.

Sample Input

5 2
1 2 3 4 5

Sample Output

11

Giải thích

các cặp thỏa mãn (1, 1), (1,2), (1, 3), (2, 2), (2, 3), (3, 3), (3, 4), (3,5), (4, 4), (4, 5), (5,5).