题目内容

塔子哥参加ACM竞赛的过程中遇到过各种各样的计数题。唯独二进制计数题他整不明白。这不，今天WZ银行恰好又出了一道这种题，他还是依旧大脑空白。你可以帮助他吗？

塔子哥拿到了四个非负整数$L$,$R$,$X$,$Y$，请计算有多少个非负整数$N$满足以下四个条件：

1.$N$的二进制表示中1的个数不小于$L$

2.$N$的二进制表示中1的个数不大于$R$

3.$N$和$X$的按位与为$X$

4.$N$和$Y$的按位或为$Y$

输入描述

第一行有一个正整数$T$($1≤T≤1000$)，代表有多少组测试数据。接下来是$T$组测试数据，每组由一行构成。

每一组测试数据仅包含四个整数$L,R,X,Y$ ($0≤L≤R≤30,0≤X,Y≤2^{30}-1$)

输出描述

$T$行，每行输出一个整数，代表你求得的答案。

样例

样例1

输入

1
2 4 1 3

输出

1

样例2

输入

2
2 3 8 62
3 5 20 61

输出

10
7

题解：位运算+组合计数

首先，考虑$N\&X=X$，对于$X$二进制位中每一个为1的位置，$N$与其对应的位置也必须要为1，我们可以使用一个标记数组进行标记

其次，考虑$N|Y=Y$，对于$Y$二进制位中每一个为0的位置，$N$与其对应的位置也必须要为0，我们可以使用一个标记数组进行标记

无解情况：上述标记的数字出现了冲突，则一定无解：同一个位置不可能既填1又填0

那么我们可以考虑一下对于有解情况的方案数：假设现在已经填了$m$个数字，其中有$k$个1，我们最终填写1的个数范围为$[L,R]$