解题思路

设一个整数对 $(a,b)$ 的得分为：

题目要求统计有多少个有序整数对 $(a,b)$，满足：

题目内容

给定一个整数 $x$，满足$0≤x<2^{31}$。

定义整数 $x$ 的「最佳拍档」为这样两个整数$(a,b)$，满足：

• $l_a≤a≤r_a$；

• $l_b≤b≤r_b$；

• $x\ xor\ a\ xor\ b$ 的值是全部整数对中能计算得到的最大值。

求解 $x$ 的不同「最佳拍档」的个数。

【名词解释】

xor 代表位运算中的异或运算。

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数$T$（$1≤T≤10^4$），代表数据组数。

每组测试数据描述如下：

• 第一行输入一个整数 $x$（$0≤x<2^{31}$），表示给定的整数 $x$。
• 第二行输入两个整数$l_a,r_a$（$0≤l_a≤r_a<2^{31}$），表示$a$ 的取值范围。
• 第三行输入两个整数 $l_b,r_b$（$0≤l_b≤r_b<2^{31}$），表示 $b$的取值范围。

输出描述

对于每组测试数据，新起一行输出一个整数，表示 $x$ 的不同「最佳拍档」的个数。

样例1

输入

2
0
1 2
0 2
5
1 7
6 9

输出

2
2

说明

对于第一组测试数据，一共有六个不同的整数对满足区间限制，分别是$(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)$，计算异或值如下：

• $0\ xor\ 1\ xor\ 0=1$；
• $0\ xor\ 1\ xor\ 1=0$；
• $0\ xor\ 1\ xor\ 2=3$；
• $0\ xor\ 2\ xor\ 0=2$；
• $0\ xor\ 2\ xor\ 1=3$；
• $0\ xor\ 2\ xor\ 2=0$；

能取到的最大的异或值为 $3$，共有 $2$ 对整数对满足条件，分别是$(1,2)$和$(2,1)$。