给出 $l$, $r$ 和 $k$，定义 $f_i = \begin{cases} 1 & 0 \le i < k \\ \sum\limits_{j=1}^{k} f_{i-j} & \text{otherwise} \end{cases}$
求 $\sum\limits_{n=l}^{r} (f_n \bmod 2)$。
注： $x \bmod y$ 的结果是一个小于 $y$ 的非负整数，代表 $x$ 除以 $y$ 的余数。
输入有多组数据。第一行有一个整数 $T$ ($1 \le T \le 10^5$)，表示测试数据组数。然后对于每组数据：
第一行包行三个正整数 $l$，$r$ 和 $k$ ($1 \le l \le r \le 10^{18}, 1 \le k \le 10^{18}$)。
对于每组数据，输出一个非负整数，表示 $\sum\limits_{n=l}^{r} (f_n \bmod 2)$ 的值。
10 1 1 2 1 2 2 1 3 2 1 4 2 1 5 2 1 6 2 1 7 2 1 8 2 1 9 2 1 10 2
1 1 2 3 3 4 5 5 6 7
Comet OJ