当前没有测试数据。

题目背景

gzx 是大费玩家，ltz 是小费玩家，他们王不见王。

长期以来，gzx 认为异或运算是 $C++$ 最恶心的运算，拥有最低的优先级；ltz 认为取模运算是 $C++$ 最恶心的运算，拥有最大的常数。

在 C++ 中，可以用 “^” 表示异或。

为了区分谁才是最恶心的运算，他们决定算对方觉得最恶心的运算，先算错的人失去竞争最恶心运算资格。

gzx：咪咪咪咪咪咪咪。

ltz：？

gzx：我算的 $187066 \% 187008 = 58$，你算的 $187066 \oplus 187088 = 58$，你肯定算错了。

ltz：……

题目描述

正所谓王不见王，ltz 不能和 gzx 解释这个问题，所以他想到可以让你解决。

ltz 会给你多组的四个正整数 $\{ l_a , r_a , l_b , r_b \}$，你需要告诉 gzx 有多少 $l_a \le a \le r_a$，$l_b \le b \le r_b$ 满足 $a \% b = a \oplus b$。

格式

输入格式

第一行给出一个非负整数 $T$ 表示数据组数。

之后 $T$ 行，每行四个正整数 $l_a , r_a , l_b , r_b$，表示一组询问

输出格式

对于每一组询问，输出答案对 $998244353$ 取模的结果。

样例

3
1 5 1 5
1 10 1 5
1 5 1 10

7
10
7

2
6 10 1 5
1 5 6 10

3
0

提示

对于 $5\%$ 的数据，$T = 0$。
对于 $15\%$ 的数据，$r_a \le 80$，$r_b \le 80$。
对于 $30\%$ 的数据，$r_a \le 10000$，$r_b \le 80$。
对于 $45\%$ 的数据，$r_a$ 或 $r_b \le 5000$。
对于 $70\%$ 的数据，$r_a,r_b \le 10^9$。
对于 $100\%$ 的数据，$T \le 10^5$，$l_a \le r_a \le 10^{18}$，$l_b \le r_b \le 10^{18}$。