F2. Elections in Saransk (hard version)

Source: Codeforces 2236F2
Contest: Codeforces Round 1103 (Div. 3)
Time limit: 3 seconds
Memory limit: 512 megabytes

Statement

This is the hard version of the problem. The only difference is that $1 \le x \le 5 \cdot 10^5$.

On the way home after buying his favorite soda "Zola Cero", Egor saw that elections for the position of "Best Number" are taking place in Saransk.

There are $n$ people at the polling station. Each person brought a number $a_i$. When the $i$-th person enters the voting booth, they choose a candidate that is a divisor of the number $a_i$. Let the chosen candidate be $p_i$.

After everyone has voted, we get an array of votes $[p_1, p_2, \ldots, p_n]$.

Egor really likes the number $x$ and considers the voting ideal if $x \cdot {lcm}(p_1, p_2, \ldots, p_n)$$^{\text{∗}}$ = $p_1 \cdot p_2 \cdot \ldots \cdot p_n$. Help him find the number of different$^{\text{†}}$ arrays $p$ modulo $10^9 + 7$ that are ideal.

$^{\text{∗}}$$lcm$ — least common multiple.

$^{\text{†}}$Two arrays of votes are considered different if there exists an index $i$ where the two arrays have different elements.

Input

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

Then $t$ test cases follow.

The first line of each test case contains two integers $n$ and $x$ ($1 \leq n \leq 10^5$, $1 \leq x \leq 5 \cdot 10^5$) — the number of voters at the polling station and Egor's favorite number.

The second line of each test case contains $n$ integers: $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 5 \cdot 10^5$) — the numbers brought by the voters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output the number of ways modulo $10^9 + 7$ to vote so that the resulting array of votes satisfies the condition.

Examples

5
2 2
2 4
1 5
5
7 4
2 4 8 13 111 6 7
3 1000
1 2 3
3 3
4 8 10

2
0
360
0
0