Counting Binary Trees

题号：NC220371
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

You are given an array of positive integers $k_1,k_2,\dots k_m$ .

A binary tree is special if all of these conditions are satisfied:

A positive integer is written on every node of the tree.
Every non-leaf node has both left child and right child, and the number written on it is equal to the product of numbers written on left child and right child. Here, we define a leaf as a node with no children, and a non-leaf node is a node that is not a leaf.
The number written on any leaf is a multiple of at least one $k_i$ . For two integers $x,y$ , we consider $x$ to be a multiple of $y$ if there exists some integer $z$ such that $x=yz$ .

Two binary trees are different if one of these conditions is satisfied:

The numbers written on their root are different.
Their left subtrees are different or their right subtrees are different.

Note that the definition above is recursive.

For a given $n$ , you need to find the number of special binary trees whose number written on the root is not greater than $n$ . Since the answer can be quite large, output it modulo $998244353$ .

输入描述:

The first line contains a single integer  () --- the number of test cases. Then  test cases follow.
The first line of each test case contains two integers  ().
The second line of each test case contains  integers  ().

输出描述:

For each test case, print a single integer: the number of special binary trees whose number written on the root is not greater than . Remember that you only need to print it modulo .

示例1

输入

复制

输出

复制

7
28

说明

In the first test case, you can find:

$1$ special binary tree whose root is $2$ ; $1$ special binary tree whose root is $3$ ; $2$ special binary trees whose root is $4$ ; $3$ special binary trees whose root is $6$ .

So the answer is $1+1+2+3 = 7$ . Here is an illustration for the $7$ trees.