### 问题描述 依依是一个善良、聪明的小女巫，她拥有一颗神奇的水晶球。这颗水晶球拥有预知未来的能力，但它的预知能力并不是无限的，需要依依通过魔法咒语来激活。 魔法咒语的形式是 "阿坤老师、妮妮、小猫咪"，其中 "阿坤老师" 代表一个整数 $a$，"妮妮" 代表一个整数 $b$，"小猫咪" 代表一个整数 $x$。 当咒语被念出时，水晶球会列出在 "阿坤老师" 和 "妮妮" 之间（包括两者）的所有整数。设其中一个整数为 $y$，若 $y$ 满足魔法规则 $x$ & $y = x$（& 是位与运算），则称 $y$ 是一个魔法数字。魔法数字越多，水晶球的预知功能就越强大。 现在依依想通过魔法咒语来测试一下这颗水晶球的预知功能，她会给你 $Q$ 个咒语，每个咒语会给出 "阿坤老师、妮妮、小猫咪"所代表的整数。对于每个咒语，请你回答她魔法数字个数。 ### 输入格式 输入的第一行包含一个整数 $Q$（$1 \leq Q \leq 10^4$），表示咒语的个数。 接下来的 $Q$ 行，每行包含三个整数 $a, b, x$（$1 \leq a \leq b \leq 10^{18}$，$0 \leq x \leq 10^{18}$），代表依依的一个咒语。 ### 输出格式 输出 $Q$ 行，每行一个整数，表示满足魔法规则的整数 $y$ 的个数。 ### 样例输入 ``` 3 1 5 2 2 7 3 10 15 12 ``` ### 样例输出 ``` 2 2 4 ```