题目内容

在一个安全系统中，给定一个基础密钥 $x$，操作员需要从两个允许的整数范围中各选取一个附加密钥片段：从区间 $[A,B]$ 中选取 $a$，从区间 $[C,D]$ 中选取 $b$。最终的安全强度计算为 $V = x \oplus a \oplus b$，其中 $\oplus$ 表示按位异或运算。

为了达到最高安全级别，我们需要使 $V$ 的值尽可能大。当 $V$ 取到全局可能的最大值时，我们称对应的有序数对 $(a, b)$ 为最优方案。请你计算一共有多少种不同的最优方案。注意，有序对 $(a_1, b_1)$ 与 $(a_2, b_2)$ 只要 $a_1 eq a_2$ 或 $b_1 eq b_2$ 就被视为不同的方案。

约束条件：

• $x$ 以及所有区间端点均为整数，且满足 $0 \le x, A, B, C, D < 2^{31}$。
• 测试用例的总组数不超过 $10^4$。

输入描述

第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示测试用例的组数。 接下来对于每组测试用例，按以下格式给出： 第一行包含一个整数 $x$。 第二行包含两个整数 $A$ 和 $B$，用一个空格分隔。 第三行包含两个整数 $C$ 和 $D$，用一个空格分隔。

输出描述

对于每组测试用例，输出一行一个整数，表示最优方案的数量。

样例1

输入

1
0
0 1
0 0

输出

1

说明

对于这组测试数据，$x=0$，$a \in [0,1]$，$b \in [0,0]$，即 $b$ 只能取 0。此时 $V = x \oplus a \oplus b = a$。为使 $V$ 尽可能大，$a$ 应取最大值 1。当且仅当 $a=1, b=0$ 时达到最大安全强度 $V=1$，因此最优方案数量为 1。

样例2

输入

1
7
0 7
0 7

输出

8

说明

$x=7$（二进制 111），$a$ 和 $b$ 均在 $[0,7]$ 内。最大可能的安全强度为 7，需要满足 $x \oplus a \oplus b = 7$，即 $a \oplus b = 0$，得 $a=b$。由于 $a$ 可任取 $[0,7]$ 中的 8 个整数，且每个 $a$ 唯一确定 $b$，所以最优有序对共有 8 种。

样例3

输入

1
8
0 15
0 15

输出

16

说明

$x=8$（二进制 1000），$a,b \in [0,15]$。最大可能的安全强度为 15（二进制 1111），需要满足 $8 \oplus a \oplus b = 15$，即 $a \oplus b = 7$。在 $[0,15]$ 内，对于每一个 $a$ 都有唯一的 $b = a \oplus 7$ 落在该区间中，共有 16 对，因此答案为 16。

样例4

输入

1
2
1 2
3 4

输出

1

说明

$x=2$，$a \in \{1,2\}$，$b \in \{3,4\}$。分别计算：

• $a=1, b=3$：$V=2 \oplus 1 \oplus 3=0$；
• $a=1, b=4$：$V=2 \oplus 1 \oplus 4=7$；
• $a=2, b=3$：$V=2 \oplus 2 \oplus 3=3$；
• $a=2, b=4$：$V=2 \oplus 2 \oplus 4=4$。 最大值为 7，仅当 $(a,b)=(1,4)$ 时取得，故最优方案数为 1。