C. おはよう 学妹
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

给定两个长度为 $$$n$$$ 的数组 $$$a,b$$$，一个正整数 $$$k$$$ ，确保 $$$k$$$ 的最大质因子大小不超过 $$$10^6$$$ 。

请问有多少个二元组 $$$(i,j),1\le{i,j}\le{n}$$$ 满足 $$$\text{lcm}(a_i,b_j)=k$$$ ？

其中 $$$\text{lcm}(x,y)$$$ 代表的是 $$$x$$$ 和 $$$y$$$ 的最小公倍数。

Input

输入第一行包含一个正整数 $$$T$$$ $$$(1\le{T}\le{10})$$$ ，代表测试组数。

对于每组测试第一行包含两个正整数 $$$n,k$$$ $$$(1\le{n}\le{10^6},1\le{k}\le{10^{18}})$$$ ，其中 $$$n$$$ 代表 $$$a,b$$$ 数组大小，确保 $$$k$$$ 的最大质因子大小不超过 $$$10^6$$$ 。

第二行包含 $$$n$$$ 个正整数 $$$a_1,a_2,...,a_n$$$ $$$(1\le{a_i}\le{10^{18}})$$$ ，代表 $$$a$$$ 数组。

第三行包含 $$$n$$$ 个正整数 $$$b_1,b_2,...,b_n$$$ $$$(1\le{b_i}\le{10^{18}})$$$ ，代表 $$$b$$$ 数组。

确保 $$$\sum{n}\le{10^6}$$$ 。

Output

输出 $$$T$$$ 行，每行包含一个整数代表二元组的数量。

Example
Input
1
2 6
2 2
3 3
Output
4