雪域羚羊的来访

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

雪域高原的羚羊公主来青青草原做客啦。为了表示羊村的好客之情,喜羊羊带领着羚羊公主在羊村中到处游玩。这一天,在羊村的实验室里,她了解到羊村村长慢羊羊正在研制一种特别的芯片。

 

村长慢羊羊在芯片中设计了 n 个微型光源,每个光源操作一次就会改变其状态,即:点亮转为关闭,或关闭转为点亮

 

这些光源的编号从 1 到 n,开始的时候所有光源都是关闭的。

 

慢羊羊村长将会在芯片上执行如下动作:

 

所有编号为2的倍数的光源操作一次,也就是把 2 4 6 8 ... 等序号光源打开

 

所有编号为3的倍数的光源操作一次, 也就是对 3 6 9 ... 等序号光源操作,注意此时6号光源又关闭了。

 

所有编号为4的倍数的光源操作一次。

 

.....

 

直到编号为 n 的倍数的光源操作一次。

 

羚羊公主感到村长研制的这种芯片十分的神奇,于是羚羊公主脑中产生了一个神奇的想法。现在羚羊公主想知道:经过这些操作后,某个区间中的哪些光源是点亮的。


Input

输入第一行为数据组数T(T<=20)。

每组数据仅一行,包含3个用空格分开的整数:N L R (L < R < N < 10 ^ 15) N表示光源数,L表示区间的左边界,R表示区间的右边界。

Output

输出1个整数,表示经过所有操作后,[L,R] 区间中有多少个光源是点亮的。

Sample Input

2
5 2 3
10 3 6

Sample Output

2
3

Hint

求完全平方数个数

Source

axuhongbo