You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目内容

塔子哥参加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