[Solution] Count GCD Codeforces Solution

D. Count GCD

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given two integers 𝑛$n$ and 𝑚$m$ and an array 𝑎$a$ of 𝑛$n$ integers. For each 1≤𝑖≤𝑛$1\le i\le n$ it holds that 1≤𝑎𝑖≤𝑚$1\le a_i\le m$.

Your task is to count the number of different arrays 𝑏$b$ of length 𝑛$n$ such that:

• 1≤𝑏𝑖≤𝑚$1\le b_i\le m$ for each 1≤𝑖≤𝑛$1\le i\le n$, and
• gcd(𝑏1,𝑏2,𝑏3,...,𝑏𝑖)=𝑎𝑖$gcd(b_1,b_2,b_3,...,b_i)=a_i$ for each 1≤𝑖≤𝑛$1\le i\le n$.

Here gcd(𝑎1,𝑎2,…,𝑎𝑖)$gcd(a_1,a_2,\dots ,a_i)$ deontes the greatest common divisor (GCD) of integers 𝑎1,𝑎2,…,𝑎𝑖$a_1,a_2,\dots ,a_i$.

Since this number can be too large, print it modulo 998244353$998244353$.

Input

Each test consist of multiple test cases. The first line contains a single integer 𝑡$t$ (1≤𝑡≤100$1\le t\le 100$) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers 𝑛$n$ and 𝑚$m$ (1≤𝑛≤2⋅105$1\le n\le 2\cdot {10}^5$, 1≤𝑚≤109$1\le m\le {10}^9$) — the length of the array 𝑎$a$ and the maximum possible value of the element.

The second line of each test case contains 𝑛$n$ integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (1≤𝑎𝑖≤𝑚$1\le a_i\le m$) — the elements of the array 𝑎$a$.

It is guaranteed that the sum of 𝑛$n$ across all test cases doesn't exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case, print a single integer — the number of different arrays satisfying the conditions above. Since this number can be large, print it modulo 998244353$998244353$.

Note

In the first test case, the possible arrays 𝑏$b$ are:

• [4,2,1]$[4,2,1]$;
• [4,2,3]$[4,2,3]$;
• [4,2,5]$[4,2,5]$.

In the second test case, the only array satisfying the demands is [1,1]$[1,1]$.

In the third test case, it can be proven no such array exists