H. Kaosar and Path
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of size $$$n$$$ and an integer $$$x$$$.

You need to perform $$$n$$$ operations. In the $$$i$$$-th operation, you must perform exactly one of the following operations:

  • G-operation: set $$$x := \gcd(x, a_i)$$$.
  • L-operation: set $$$x := \mathrm{lcm}(x, a_i)$$$.

Define the operation sequence $$$s$$$ as a string of length $$$n$$$, where $$$s_i \in \{$$$ 'G', 'L' $$$\}$$$ denotes the type of operation chosen in the $$$i$$$-th operation.

There is an additional constraint: You cannot use the G-operation twice in a row. Formally, if there exists an $$$i$$$ ($$$1 \le i \le n-1$$$) such that $$$s_i=s_{i+1}=\{$$$'G'$$$\}$$$, then it is illegal.

Find the minimum possible final value of $$$x$$$, assuming you perform the operations optimally. And count the number of different operation sequences that can achieve this minimum value, modulo $$$998,244,353$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1\le t\le 2 \cdot 10^4$$$). The description of the test cases follows. For each test case:

  • The first line contains two integers $$$n$$$ and $$$x$$$ ($$$1\le n\le 10^5$$$, $$$1\le x\le 10^6$$$).
  • The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$${1\le a_i\le 10^6}$$$).

The sum of $$$n$$$ across all test cases does not exceed $$$10^5$$$.

Output

For each test case, print a single line containing two integers — the minimum possible final value of $$$x$$$, assuming you perform the operations optimally, and the number of different operation sequences that can achieve this minimum value, modulo $$$998,244,353$$$.

Example
Input
2
2 4
6 2
3 6
6 6 6
Output
2 2
6 5
Note

In the first test case:

  • For operation sequence "LG", the final value of $$$x$$$ is $$$2$$$.
  • For operation sequence "GL", the final value of $$$x$$$ is $$$2$$$.
  • For operation sequence "LL", the final value of $$$x$$$ is $$$12$$$.

We can see the minimum possible final value of $$$x$$$ is $$$2$$$, and the number of different operation sequences that can achieve this minimum value is $$$2$$$.