### 问题描述

依依是一个善良、聪明的小女巫，她拥有一颗神奇的水晶球。这颗水晶球拥有预知未来的能力，但它的预知能力并不是无限的，需要依依通过魔法咒语来激活。

魔法咒语的形式是 "阿坤老师、妮妮、小猫咪"，其中 "阿坤老师" 代表一个整数 $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