cats 刚刚开始学习二分答案，写出了下面这段代码（以下给出伪代码，在题目的末尾会提供 C/C++，Python，Java 语言的具体代码）

给出的数组 $a$ 下标范围为 $[1,n]$，且
$$
a_i=\begin{cases}
1 & (i∈[1,n)) \\
2 & (i=n)
\end{cases}
$$

cats 知道 $n∈[l,r]$，他希望通过以上这段代码找出 $n$ 的值。可以发现这段代码有访问越界下标的可能，访问越界下标 $i\gt n$ 时，会得到 $a_i =0$。但是在一次程序运行过程中，如果访问越界下标超过 $k$ 次，程序就会崩溃。现在你需要求出有多少不同的 $n∈[l,r]）$可以让程序在不崩溃的情况下得到正确结果。

第一行一个整数 $T（1≤T≤10^3 ）$，表示测试数据的组数。

接下来 $T$ 行，每行三个整数 $l,r,k（1≤l≤r≤10^{18} ,0≤k≤10^{18} ）$，表示 $n$ 的范围和程序在不崩溃的情况下访问越界下标次数的上限。

对于每组测试数据，输出一个整数，表示满足条件的不同的 $n$ 的个数。