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 . 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 . She calls the Carol-dividing number of the number of divisions of required to reduce it to . As some examples, the Carol-dividing number of is , the Carol-dividing number of is , and the Carol-dividing number of is .

Given an array of numbers and an integer , calculate the number of contiguous subarrays in which the Carol-dividing number of the greatest common factor is equal to . In other words, find the number of ranges, and , such that the greatest number which divides has Carol-dividing number equal to .

#### Constraints

#### Input Specification

The first line will contain , the size of the array and the designated number of common factors. The next lines will contain the integers .

#### 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.

## Comments