设 $f(x)$ 为正整数 $x$ 在十进制表示下的最大数位。例如，$f(4523) = 5$ 且 $f(1001) = 1$。

给定四个正整数 $l_a$、$r_a$、$l_b$ 和 $r_b$，满足 $l_a \le r_a$ 且 $l_b \le r_b$，你需要计算：

$$\sum_{a=l_a}^{r_a} \sum_{b=l_b}^{r_b} f(a + b)$$

也就是说，求所有满足 $l_a \le a \le r_a$ 且 $l_b \le b \le r_b$ 的二元组 $(a, b)$ 的 $f(a + b)$ 之和。

输入格式

每个输入文件包含多个测试用例。输入的第一行包含一个整数 $T$ ($1 \le T \le 10^3$)，表示测试用例的数量。对于每个测试用例：

第一行且仅有一行包含四个整数 $l_a$、$r_a$、$l_b$ 和 $r_b$ ($1 \le l_a \le r_a \le 10^9$，$1 \le l_b \le r_b \le 10^9$)。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示答案。

样例

输入样例 1

2
178 182 83 85
2 5 3 6

输出样例 1

91
100

输入样例 2

1
1 1000000000 1 1000000000

输出样例 2

8425695016000000001