题目描述

这是该问题的困难版本。唯一的区别在于 $1 \le x \le 5 \cdot 10^5$。

在买完他最喜欢的苏打水"Zola Cero"回家的路上，Egor 看到萨兰斯克正在举行"最佳数字"职位的选举。

投票站里有 $n$ 个人。每个人带来了一个数字 $a_i$。当第 $i$ 个人进入投票间时，他们选择一个数字 $a_i$ 的约数作为候选人。设被选中的候选人为 $p_i$。

所有人都投票后，我们得到投票数组 $[p_1, p_2, \ldots, p_n]$。

Egor 非常喜欢数字 $x$，并且认为如果 $x \cdot {lcm}(p_1, p_2, \ldots, p_n)$$^{\text{∗}}$ = $p_1 \cdot p_2 \cdot \ldots \cdot p_n$，则此次投票是理想的。请帮他计算出理想投票的不同$^{\text{†}}$数组 $p$ 的数量，模 $10^9 + 7$。

$^{\text{∗}}$$lcm$ — 最小公倍数

$^{\text{†}}$若两个投票数组在某个下标 $i$ 处的元素不同，则称它们为不同的。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——测试用例的数量。

接下来有 $t$ 个测试用例。

每个测试用例的第一行包含两个整数 $n$ 和 $x$（$1 \leq n \leq 10^5$，$1 \leq x \leq 5 \cdot 10^5$）——投票站的选民人数与 Egor 的幸运数字。

每个测试用例的第二行包含 $n$ 个整数：$a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 5 \cdot 10^5$）——选民带来的数字。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

输出格式

对于每个测试用例，输出投票方案数模 $10^9 + 7$ 的结果，使得最终的投票数组满足条件。

样例

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