B. Red Dead Redemption 2
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After a successful train robbery, outlaw Dutch and his gang acquired $$$n$$$ valuable items with values $$$a_1, a_2, \ldots, a_n$$$. An old-timer warned them that items can only be stored together if their values are pairwise coprime (that is, every pair of items shares no common factors other than 1), or bad luck will follow and the gang will be dead.

Arthur, Dutch's most trusted gang member, has been tasked with storing the loot. For security reasons, he must split the loot between two hideouts such that both hideouts contain at least one item, and each item is stored in exactly one hideout.

Arthur now wants to know how many different ways he can distribute the stolen goods so that the items in each hideout can be safely stored together. Two distributions are considered different if there exists at least one item placed in different hideouts (each item is identified by its index, not value).

As the count can be large, Arthur needs to calculate it modulo $$$998244353$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$) — the number of items.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 5 \cdot 10^6$$$) — the values of the items.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output

For each test case, output a single integer — the number of safe distributions modulo $$$998244353$$$.

Example
Input
1
5
33 21 70 55 52
Output
2
Note

One valid split of items in the given case is $$$\{1, 3\}$$$ and $$$\{2, 4, 5\}$$$ (where these numbers represent indices). Swapping the groups is also valid.