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~.
~1 \le N \le 1\,000\,000~
~0 \le K \le \min(20, N)~
~1 \le a_i \le 100\,000~
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 a single integer, as specified in the statement.
16 1 25 7 10 32 25 29 29 29 27 25 27 11 18 27 9 13
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.