D. Good Sets
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

$$$S$$$ is the set of certain integers. If the difference between any two integers in the set is not greater than $$$k$$$, $$$S$$$ is considered good.

You are given an array $$$a$$$ of length $$$n$$$.

Your task is to find the number of non-empty good subarrays and non-empty good subsequences.

Print them modulo 998244353.

Input

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

The first line of each test case contains two integers $$$n$$$ $$$(1 \le n \le 2 ⋅ 10^5)$$$ and $$$k$$$ $$$(0 \le k \le 10^{18})$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2 \dots a_n$$$ $$$(-10^{18} \le a_i \le 10^{18})$$$.

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

Output

For each test case, output two integers — good subarrays and good subsequences.

Example
Input
2
4 2
4 5 8 3
7 21
32 19 -2 -5 0 -11 9
Output
5 8
19 41