#P17764. 炼金术士

炼金术士

炼金术士(alchemist) 1s 512mb

题目描述

炼金术士年复一年地在魔法阵中提炼神秘晶石。

炼金术士的提炼过程一共需要经历 nn 个反应阶段,他的初始魔力值为 00,在第 ii 个阶段原本可以注入 ii 单位的魔力。

魔力的聚集会引发排斥效应,如果他的魔力值不小于 ii,那么魔法阵会因为能量过载而排斥这次注入,导致他反而会损耗 ii 单位的魔力。

炼金术士对任意恰好一个反应阶段使用一次稳定咒语,这样该阶段一定不会发生排斥,从而成功注入 ii 单位的魔力。

请你帮炼金术士求出,对多少个不同的阶段使用稳定咒语时,他的最终魔力值会落在区间 [L,R][L, R] 中?

输入格式

第一行一个正整数 TT,表示询问组数。

接下来 TT 行,每行三个整数 n,L,Rn, L, R。

输出格式

输出共 TT 行,表示答案。

样例 1

1
3 5 7
1

样例 1 解释

对第 11 个阶段使用咒语,最终魔力为 1+2−3=01 + 2 − 3 = 0,不位于区间 [5,7][5, 7]。

对第 22 个阶段使用咒语,最终魔力为 1+2−3=01 + 2 − 3 = 0,不位于区间 [5,7][5, 7]。

对第 33 个阶段使用咒语,最终魔力为 1+2+3=61 + 2 + 3 = 6,位于区间 [5,7][5, 7]。

所以答案是 11。

样例 2

3
5 67 89
1357 500 5000
999999999 20160401 333333333
0
1354
17

数据范围与约定

对于 100%100\% 的测试数据,满足 $1\le T\le 1000,1\le n\le 10^{18},0\le L\le R\le 10^{18}$。

具体每个测试点的限制如下表所示:

测试点编号 T≤T\le n,R≤n,R\le
1∼21\sim 2 10001000 100100
3∼93\sim 9 1010 10510^5
10∼1210\sim 12 10910^9
13∼1613\sim 16 10001000
17∼2017\sim 20 101810^{18}