| 问题描述 |
|---|
罗少有一个环，这个环由连续的数字 L，L+1，L+2，...，R 组成。 现在罗少对环进行以下操作： 每次操作罗少可以选择环上任意一段（必须连续，也可以是整个环） 如果这些数字的和是 x 的倍数，罗少就会删去这一段，然后，剩余的部分首尾相接形成一个新的环 罗少可以操作无数次，他想知道直到不能操作时，环上至少还有多少个数字。 |
| 输入描述 |
第一行是一个整数 T 代表案例组数。（1 ≤ T ≤ 1e4） 每组案例包含三个正整数 L，R，x。（1 ≤ L ≤ R ≤ 1e9，1 ≤ x ≤ R - L + 1） |
| 输出描述 |
针对每组案例，输出罗少操作到不能操作时最少剩下多少数，然后换行。 |
| 样例输入复制样例 |
1 1 5 2 |
| 样例输出 |
1 |
| 提示说明 |
第一次操作删除环上的 4，5，1。 第二次删除环上的 2，最后剩下一个数。 |
| 相关 |