There are two small ants on Rikka's desk. If we consider Rikka's desk as a two-dimensional Cartesian coordinate system, both of them have coordinate (1,0).

Now, Rikka places three obstacles on her desk:
1. y = 0, none of the two ants can walk cross this line.
2. , only the second ant can walk cross this line.
3.  , only the first ant can walk cross this line.

It's remarkable that it is allowed for the ants to stand exactly on the obstacles. For example, if a=b=c=d=1, then both of the ants can reach (1,0),(1,1),(2,1),(2,2) and none of them can reach (1,2),(2,3).

Now, the ants start to move. Their strategy is very simple: In each second, let (x,y) be the current coordinate of one ant, if it can reach (x,y+1), it will walk to this point, otherwise it will walk to (x+1,y).(Since , if the ant can reach (x,y), it can also reach (x+1,y)).

The following image shows the first ant's path when a=3,b=2:


Now, given a,b,c,d, let p₁ be the first ant's path and p₂ be the second ant's path. Rikka wants you to calculate the number of the points with integer coordinates which are on both p₁ and p₂.

The first line contains a single integer t(1 ≤ t ≤ 105), the number of the testcases.

For each testcase, the first line contains four integers a,b,c,d(1 ≤ a,b,c,d ≤ 109).

For each testcase, output a single line with a single number, the answer modulo 998244353. If p1,p2 have infinite many common points, output -1.

5
1 1 1 1
1 2 1 1
1 3 2 1
1 100 1 99
12 34 56 78

-1
2
1
5049
3