Problem Description

Pty loves data structures, especially segmenttree.

Pty thinks that the segmenttree satifies each point to represent the interval [l,r]. The point with l = r is called a leaf. The other point select mid in [l,r-1] and take [l,mid] and [mid + 1,r] as son.

Pty gives each point in the tree a value. For the leaves, the value is 1; For the point whose right son interval size is k, the value is A; The other point’s value is B. Pty denotes the value of the tree as the value product of all points.

Pty denotes $f_n$ as the sum of all the tree that the interval of the root is [1,n]. He thinks that the two trees are different if and only if the shape is different.

Now Pty has Q queries, for each query Pty wants to know the value of $\sum_{i=L}^R f_i^2$

Noticed that the answer is large, you only need to find the answer after modulo 998244353.

Input

A positive integer T in the first line indicates the number of test.

For each test,the first line contains four integers Q,k,A,B.

For the next Q lines, each line contains two intergers L,R.


$1\le T\le 5, 1\le Q \le 5 \times 10^4, 0 \le A,B < 998244353, 1 \le L \le R \le 10^7, 1 \le k \le 10^7$

Output

For each query, print the answer.

1
1 1 3 1
4 4

3249

Hint

There are 5 di&#64256;erent trees, 1 with a value of 3,3 with a value of 9,1 with a value of 27. The sum is 3*1 + 9*3 + 27*1 = 57,57*57 = 3249