Operate on Arrays#12384
You are given an integer array of length .
You may perform at most operations of the following type:
Choose an index (1 \le i \le n).
Choose any prime divisor of a_i.
Replace a_i with \dfrac{a_i}{p}.
Your task is to determine the number of distinct arrays that can be obtained after performing at most such operations.
Two arrays are considered different if there exists at least one index such that their values at that index differ.
Note
Each operation modifies exactly one element by dividing it by one of its prime divisors.
The same index may be chosen multiple times, as long as the operation remains valid.
The first line contains an integer (1 \le t \le 10^4) — the number of test cases.
Each test case consists of two lines.
The first line contains two integers and (1 \le n,k \le 1000).
The second line contains integers a_1, a_2, \ldots, a_n (1 \le a_i \le 10^6).
It is guaranteed that the sum of n \cdot k over all test cases does not exceed 10^6.
For each testcase,
Output the number of distinct arrays that can be obtained after performing at most operations modulo .
Example 1
Subtask ( points): (k = 1)
Subtask ( points): (a_i \text{ is prime})
Subtask ( points): (a_i \text{ is of the form } p \cdot q,\ \text{where } p \text{ and } q \text{ are primes})
Subtask ( points): (a_i \le 100)
Subtask ( points): No additional constraints