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~. Hãy tìm số cặp số nguyên (~l~, ~r~) với ~1 ≤ l ≤ r ≤ N~ sao cho trong đoạn con từ ~a_l~ đến ~a_r~, có tối đa một số chia hết cho ~k~.

INPUT

• Dòng 1: ~N~, ~k~ (~1 ≤ N ≤ 3×10^5~, ~1 ≤ k ≤ 10^9~)
• Dòng 2: ~a_1, a_2, ... ,a_N~ (~1 ≤ a_i ≤ 10^9~)

OUTPUT

• Một số nguyên: số lượng cặp (~l~, ~r~) thỏa mãn điều kiện.

VÍ DỤ

Input:

5 2
1 2 3 4 5

Output:

11