2024 上海市大学生编程新锐挑战赛

A. Rush for a place
PDF 题面可用
你可以在这里下载。

单点时限: 1.0 sec

内存限制: 512 MB

2024 年 ICPC 中国陕西全国程序设计邀请赛 将在 5 月开赛,$\texttt{SpadeZ}$ 十分想通过这场比赛公费报销去西安找她的朋友玩。报名通道将在 3 月 18 日的某个时间开放,但是参赛名额有限,先到先得。为了抢到参赛名额,$\texttt{SpadeZ}$ 决定每隔一段固定的时间就水一下 $\texttt{QQ}$ 群,以免错过报名的消息。但是高强度的学习使得 $\texttt{SpadeZ}$ 非常疲惫,所以她需要在某一时刻睡一段时间,睡觉的时候 $\texttt{SpadeZ}$ 当然水不了群。睡醒后她会立刻水一下群,在这之后还是按照之前的时间间隔水群。$\texttt{SpadeZ}$ 想知道有多少种睡觉的方案能让她获得参赛名额。

具体地,假设水群间隔为 $t$。

  • 如果不睡觉,$\texttt{SpadeZ}$ 将在 $t, \ 2t, \ 3t, \ \cdots \ $ 各水一次群;

  • 如果 $\texttt{SpadeZ}$ 在 $x$ 睡觉 $y$ 个单位时间,则在 $[1, x - 1]$ 水群的时间还是和不睡觉一样,在 $[x, x + y - 1]$ 都不会水群,之后则在 $x + y, \ x + y + t, \ x + y + 2t, \ \cdots \ $ 各水一次群。

现在给定水群间隔 $t$ 和一个正整数 $n$,已知报名通道将在 $p \ (1 \leqslant p \leqslant n)$ 开放。当且仅当 $\texttt{SpadeZ}$ 在 $p$ 水了群,她才能抢到参赛名额。$\texttt{SpadeZ}$ 将选择在某个时间点 $x \ (1 \leqslant x \leqslant n)$ 睡 $y \ (1 \leqslant x \leqslant n)$ 个单位时间(即一共有 $n \times n$ 种组合方案),请求出有多少种方案能让 $\texttt{SpadeZ}$​ 获得参加陕西全国邀请赛的名额。

输入格式

每个测试点由多个测试用例组成。
第一行包含一个整数 $t \ (1 \leqslant t \leqslant 2 \times 10^5)$ 表示测试用例数,然后是测试用例的描述。
每个测试用例的第一行包含 $3$ 个整数 $n, t, p \ (1 \leqslant n \leqslant 1 \times 10^9, \ 1 \leqslant t, \ p \leqslant n)$​,分别表示时间范围、水群的时间间隔和报名开放的时间。

输出格式

对于每个测试用例,输出一个整数,表示能让 $\texttt{SpadeZ}$ 抢到参赛名额的方案数。

样例

Input
3
3 2 1
3 2 2
3 2 3
Output
0
4
2