Problem Description

Little A has a sequence of length $n$, denoted as $a_1, a_2, \cdots, a_n$. He can choose an interval $[l, r]$ where the difference between the maximum and minimum values does not exceed $k$.

He also needs to find $m$ distinct integers $p_1, p_2, \cdots, p_m$, satisfying:

• $m$ is a positive integer.
• $\prod_{i=l}^r a_i = \prod_{i=1}^m p_i$. That is, the product of the chosen interval equals the product of these $m$ numbers.
• Each $p_i$ is a positive integer power of a prime number.

The sum of the number of divisors of these $m$ numbers is Little A's score. Help him find the maximum score.

Input Format

The first line contains two integers $n$ and $k$.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$, representing the sequence.

Output Format

A single integer representing the answer.

Sample Input and Output

Sample Input #1

4 2
6 4 2 3

Sample Output #1

7

Sample Input #2

5 3
8 6 9 6 4

Sample Output #2

13

Sample Input #3

17 17
29 38 9 10 16 5 1 10 27 20 11 9 15 11 2 3 10

Sample Output #3

17

Notes/Hints

Sample Explanation

Sample 1: Choose interval $[1, 2]$, then choose $p_1 = 2$, $p_2 = 3$, $p_3 = 4$, achieving the maximum score of $7$. There are multiple solutions.

Sample 2: Choose interval $[1, 4]$, then choose $p_1 = 4$, $p_2 = 8$, $p_3 = 3$, $p_4 = 27$, achieving the maximum score of $13$.

Data Range and Constraints

This problem uses batched testing.

• Subtask 1 (1 point): $n = 1$ and $a_1$ is a prime number.
• Subtask 2 (9 points): $n = 1$.
• Subtask 3 (20 points): $n \leq 10$, $a_i \leq 20$.
• Subtask 4 (13 points): $n \leq 200$, $a_i \leq 200$.
• Subtask 5 (17 points): $n \leq 2 \times 10^3$.
• Subtask 6 (15 points): $a_i$ is a prime number.
• Subtask 7 (25 points): No additional constraints.

For $100\%$ of the data: $1 \leq n \leq 10^5$, $2 \leq a_i \leq 10^5$, $0 \leq k \leq 10^5$.

Problem Source

Sweet Round 05 B.
Idea & solution: ET2006.

见题面 Input 部分

见题面 Output 部分