该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

尘正在监测一片极不稳定的数据空间。

在这片数据风暴中，漂浮着一些编号从 $L$ 一直到 $R$ 的数据包。

当尘尝试同时捕获一个数据包集合 $S$ 时，它们会发生一种异或干涉。这个干涉的总强度，恰好等于集合 $S$ 中所有数据包编号的异或和。

尘的采集设备非常精密，但也很脆弱。它能承受的干涉强度有一个临界阈值 $c$。一旦总强度超过 $c$，设备就会因过载而失效。

现在，尘有 $T$ 个不同的观测任务。每一个任务都指定了一段风暴区 $[L, R]$ 和一个安全阈值 $c$。

对于每个任务，请帮助尘发现在不引发设备过载的前提下，她从指定的区域内，最多能同时捕获多少个数据包。

简短题意：

$T$ 组数据，给定 $L, R, c$，求 $\max |S|$，满足 $S \subseteq [L,R]$ 且 $S$ 中元素的异或和 $\leq c$。

输入

第一行一个整数 $T(1 \leq T \leq 10^4)$。

接下来 $T$ 行，每行三个整数 $L,R,c(1 \leq L \leq R \leq 10^{18}, 1 \leq c \leq 10^{18})$。

输出

输出 $T$ 行，每行一个整数，表示最多能捕获的数据包数。

输入输出样例 #1

输入 #1

2
2 6 5
3 4 1

输出 #1

4
0

样例解释 1

• 对于第一组任务，一种可能的最优选法是选择数据包 $2,3,4,6$，它们的异或和为 $3$。
• 对于第二组任务，尘不能捕获任何数据包。