Cho số nguyên dương ~k~ và một dãy gồm ~N~ số nguyên dương~a_1, a_2, ..., a_n~. Tìm số cặp số nguyên dương (~l, r~) với ~l~ ≤ ~r~, sao cho trong các số từ ~a_l~ đến ~a_r~, có tối đa một số chia hết cho ~k~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~k~ (~N~ ≤ ~3*10^5~, ~k ≤ 10^9~).
• Dòng thứ hai gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_n~(~a_i ≤ 10^9~).

Output

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

Sample

Input #1

5 2
1 2 3 4 5

Output #1

11

Hint

Giải thích:

• Các cặp số (~l, r~) thỏa mãn là: ~(1,1), (1,2), (1,3), (2,2), (2,3), (3,3), (3,4), (3,5), (4,4), (4,5), (5,5)~.

Ràng buộc:

• Subtask 1 (20% số test): ~N~ ≤ 200
• Subtask 2 (40% số test): ~N~ ≤ 2000
• Subtask 3 (40% số test): Không có ràng buộc gì thêm.

Problem source: Free Contest 120