Carol has recently started thinking about primes, and marveling at the way in which numbers can be expressed through their prime factorization. Carol especially enjoys taking a number, and dividing it by some prime, and repeating this process until the number becomes ~1~. No matter what primes Carol selects along the process, she discovers that it takes exactly the same number of divisions to reduce a starting number down to ~1~. She calls the Carol-dividing number of ~X~ the number of divisions of ~X~ required to reduce it to ~1~. As some examples, the Carol-dividing number of ~16~ is ~4~, the Carol-dividing number of ~12~ is ~3~, and the Carol-dividing number of ~1~ is ~0~.

Given an array of ~N~ numbers and an integer ~K~, calculate the number of contiguous subarrays in which the Carol-dividing number of the greatest common factor is equal to ~K~. In other words, find the number of ranges, ~L~ and ~R~, such that the greatest number which divides ~a[L], a[L+1], \dots, a[R-1], a[R]~ has Carol-dividing number equal to ~K~.

Constraints

~1 \le N \le 1\,000\,000~

~0 \le K \le \min(20, N)~

~1 \le a_i \le 100\,000~

Input Specification

The first line will contain ~N~, the size of the array and ~K~, the designated number of common factors.

The next ~N~ lines will contain the integers ~a_i~.

Output Specification

Output a single integer, as specified in the statement.

Sample Input

16 1
25
7
10
32
25
29
29
29
27
25
27
11
18
27
9
13

Sample Output

10

Explanation

The valid contiguous (0-indexed) subarrays are 1-1, 2-3, 5-5, 5-6, 5-7, 6-6, 6-7, 7-7, 11-11, 15-15.