Rhodoks\text{Rhodoks}Rhodoks很喜欢lowbitlowbitlowbit函数。
lowbit(x)lowbit(x)lowbit(x)定义为xxx和−x-x−x的按位与。含义是xxx的二进制表示中，最低的一位1所代表的值。
例如：
12=(1100)2,lowbit(12)=(12 & −12)=4=(100)212=(1100)_2,lowbit(12)=(12~\&~-12)=4=(100)_2 12=(1100)2,lowbit(12)=(12 & −12)=4=(100)2
Rhodoks\text{Rhodoks}Rhodoks写下了两个非负整数l,rl,rl,r，他想知道有多少非负整数xxx满足，在执行了 kkk 次 x += lowbit(x)操作之后，l≤x≤rl \leq x \leq rl≤x≤r。
x += lowbit(x)
第一行为正整数TTT，代表输入数据共TTT组。
接下来TTT行，每行有三个非负整数lll,rrr和kkk，含义如上所述。
每行一个非负整数表示答案。
3 9 9 6 2 5 1 0 3 5
0 3 1
1≤T≤1000001 \leq T \leq 1000001≤T≤100000
0≤l≤r≤2600 \leq l \leq r \leq 2^{60}0≤l≤r≤260
0≤k≤600 \leq k \leq 600≤k≤60