序列中初始只有一个非负整数 nnn ，将序列中满足 x>1x > 1x>1 的数不断拆分为 ⌊x/2⌋\lfloor x/2 \rfloor⌊x/2⌋ , x%2x \% 2x%2 , ⌊x/2⌋\lfloor x/2 \rfloor⌊x/2⌋ 三个数并置于原位，最终得到一个仅含 0,10, 10,1 的序列。求这个最终序列中 [l,r][l, r][l,r] 区间内有多少个 111 。序列下标从 111 起，且假定下标 l,rl, rl,r 合法。
多组询问。
第一行一个整数TTT，为询问的组数。
接下来TTT行，每行三个整数n,l,rn,l,rn,l,r，含义如上。
输出一行一个非负整数表示答案。
2 6 2 4 8 1 10
2 5
1≤T≤1051 \leq T \leq 10^51≤T≤105
0≤n≤2600 \le n \le 2^{60}0≤n≤260
1≤l,r≤10181 \le l,r \le 10^{18}1≤l,r≤1018