Description

给定长度为 $n$ 的数组 $a$

数组 $b$ 满足 $\forall 1 \leq i \leq n$ ，$1\leq b_i \leq m$ 且 $\gcd(b_1,b_2,...,b_i) = a_i$ ，其中 $\gcd(b_1,b_2,...,b_i)$ 代表 $b_1,b_2,...,b_i$ 的最大公约数

求出数组 $b$ 的方案数对 998244353 取模的结果

Input

本题含有多组测试数据

第一行一个正整数 $T$ ，表示数据组数

每组数据第一行两个正整数 $n,m$ ，第二行 $n$ 个数表示数组 $a$

$1 \leq T \leq 5 , 1 \leq n \leq 10^5 , 1 \leq m \leq 10^9 , 1 \leq a_i \leq m$

Output

每组数据一行一个正整数，表示数组 $b$ 的方案数

Sample

5
3 5
4 2 1
2 1
1 1
5 50
2 3 5 2 3
4 1000000000
60 30 1 1
2 1000000000
1000000000 2

3
1
0
595458194
200000000