A Non-Decreasing number is a number whose ith digit from the left is greater than or equal to the (i-1)th digit from the left.

You are given four integers A, B, C and D. X is any integer between A and B, inclusive, and Y is any integer between C and D, inclusive. You must output the number of numbers formed by the concatenation of X and Y which are Non-Decreasing, i.e. if we treat "X" and "Y" as STRINGS, then "Z" = "X" + "Y" must represent a Non-Decreasing number.

Since this number can be very large, give your answer modulo 98765431.

If the same number "Z" can be formed in various ways, it must be counted every time. See example for clarification.

Input

The first line of the input contains t, the number of test cases. This is followed by t lines containing 4 positive integers each, which are the values of A, B, C, D.

Output

You must output t lines. Each line contains the answers for the quadruple (A, B, C, D) in the order they appear in input.

Example

Input:
1
1 11 1 11

Output:
56

Explanation

Note that the number "111" is counted twice. Once as "11" + "1" and again as "1" + "11".

Constraints

A, B, C, D are all positive integers having ≤ 1000 digits
A ≤ B; C <= D;
Number of test cases t ≤ 1000

---

hide comments

	Ehor Nechiporenko: 2012-11-22 15:53:44 It was a long way to resolve this task. But I am happy to finally created the correct solution. Thanks a lot to problem setter!