Migrated from Lutece 2666 序章 - 特别受灾地区

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

悲剧往往是 “不合理” 的，不过，

也没有这么多 “不合理” 可以合适地形容那临近的悲剧了。

那一天，这个城市与许多人的生命一起随大地崩塌了。

性别，年龄，人性，地位，经济力······

任何牺牲者，如沧海一粟，没有任何区别，

只是发生在那一刹那的一件事，便无情地夺走了他们的生命。

为何必须得死亡？

无尽的死亡，对这个世界有意义吗？

回答是没有，死亡，即是身处此地的人们被上帝命中指定的结局，

没有生的轮廓，只有汪洋般的丧失感。

这即是，被后世人称作为「大崩塌」的悲剧。

从那次灾难至今，这个城市被酸雨和销烟所笼罩。

从上至下，污染了城市的渠水、河流，

不久淤塞了整个城市的生态，使之成为人间牢狱。

没有除去愈加扩大的污水的策略，生者即如囚犯，仅剩无力的喘息。

究竟得等到何时，这个城市才能迎来晴日的洗礼？

(OP) Ceui - Asphodelus -short ver.

---

$\space$ 由于十几年前的「大崩落」，「诺瓦斯·艾蒂尔」的下层的一块区域掉下地面，形成了如今的「牢狱」。「大崩落」之后，身陷牢狱的人们中有一个人，率先带领牢狱的人民开展重建工作，尽力恢复人们的生活，维持社会治安与稳定，并创立了组织「不蚀金锁」来加强对牢狱的各项管理工作。现在，这个人被不蚀金锁的部下统称为「先代」。当时重建工作的首要任务，便是恢复牢狱各个地区之间的交通来往。

先代决定将整个牢狱划分为若干区域，区域之间的交通连成一棵二叉树的形式，并给各个区域标上标号（不同区域的标号可能相同）。同时，先代写下了 $m$ 个数字 $a_1,a_2,...,a_m$。他认为这棵二叉树还需要满足如下条件：

• 每一个非叶节点都有左右儿子节点，且该节点的标号是左右儿子的标号的乘积。
• 对于任意一个节点的标号 $v_u$，都存在至少一个 $a_i$，满足 $a_i \mid v_u$。

现在，先代交给手下吉克一个任务：当根节点的标号不超过 $n$ 时，计算出一共有多少棵二叉树能够全部满足先代的要求。由于答案可能会很大，结果对 $998244353$ 取模即可。

两棵二叉树不同的递归形式定义如下：

• 根节点的标号不同；
• 左子树或者右子树不同。

Input

第一行输入一个正整数 $T$，表明有 $T$ 组数据。

接下来对于每一组数据，第一行输入两个正整数 $n,m$；

接下来一行输入 $m$ 个正整数，表示 $a_1,a_2,...,a_m$。

Output

对于每一组数据，输出一行表示答案。

Samples

2
6 2
2 3
100 2
6 9

7
28

Constraints

$1\le T \le 10$ $1\le n \le 10^9, 1\le m \le 4$ $2\le a_i \le 100$

Note

第一组样例对应的所有二叉树如下：

Resources

2021 UESTC ICPC Training for Math and Geometry