## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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\le i\le n$ it holds that $1\le {a}_{i}\le m$.

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

• $1\le {b}_{i}\le m$ for each $1\le i\le n$, and
• $gcd\left({b}_{1},{b}_{2},{b}_{3},...,{b}_{i}\right)={a}_{i}$ for each $1\le i\le n$.

Here $gcd\left({a}_{1},{a}_{2},\dots ,{a}_{i}\right)$ deontes the greatest common divisor (GCD) of integers ${a}_{1},{a}_{2},\dots ,{a}_{i}$.

Since this number can be too large, print it modulo $998\phantom{\rule{thinmathspace}{0ex}}244\phantom{\rule{thinmathspace}{0ex}}353$.

Input

Each test consist of multiple test cases. The first line contains a single integer $t$ ($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\le n\le 2\cdot {10}^{5}$$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 ${a}_{1},{a}_{2},\dots ,{a}_{n}$ ($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\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 $998\phantom{\rule{thinmathspace}{0ex}}244\phantom{\rule{thinmathspace}{0ex}}353$.

Note

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

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

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

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