H. Vanishing Fairy Tale
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array of $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$.

A spell works as follows. First, choose a subsequence of the array (possibly empty). Then, for each chosen element $$$A_i$$$, choose exactly one of three fates:

  • keep it as $$$+A_i$$$,
  • flip its sign, turning it into $$$-A_i$$$, or
  • make it vanish, turning it into $$$0$$$.

The result of the spell is the sequence of the transformed chosen elements. Its beauty is the number of distinct integers in it. Note that every vanished element becomes the same integer $$$0$$$, so all vanished elements together add at most one distinct integer. The beauty of an empty result is $$$0$$$.

Two spells are considered different if some index $$$i$$$ is chosen in one of them but not in the other, or is chosen in both but gets a different fate. In particular, there are exactly $$$4^N$$$ different spells.

You have to answer $$$Q$$$ queries. In each query you are given an integer $$$K$$$. Count the spells whose beauty is a multiple of $$$K$$$. Note that $$$0$$$ is a multiple of every $$$K$$$.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \le N, Q \le 10^5$$$) — the size of the array and the number of queries.

The second line of each test case contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$ ($$$1 \le A_i \le N$$$).

Each of the next $$$Q$$$ lines of each test case contains a single integer $$$K$$$ ($$$1 \le K \le 10^5$$$).

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$, and the sum of $$$Q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each query of each test case, print the number of spells whose beauty is a multiple of $$$K$$$, modulo $$$998244353$$$, on its own line.

Example
Input
1
3 3
2 1 2
1
2
3
Output
64
35
15
Note

In the sample, there are $$$4^3 = 64$$$ spells. Their beauties are distributed as follows:

  • $$$1$$$ spell has beauty $$$0$$$ (nothing is chosen);
  • $$$15$$$ spells have beauty $$$1$$$;
  • $$$34$$$ spells have beauty $$$2$$$;
  • $$$14$$$ spells have beauty $$$3$$$.

For example, choosing all three elements and giving them the fates "vanish", "keep", "vanish" produces the sequence $$$0, 1, 0$$$, which has beauty $$$2$$$.

For $$$K = 1$$$, all $$$64$$$ spells are counted. For $$$K = 2$$$, the spells with beauty $$$0$$$ or $$$2$$$ are counted: $$$1 + 34 = 35$$$. For $$$K = 3$$$, the spells with beauty $$$0$$$ or $$$3$$$ are counted: $$$1 + 14 = 15$$$.