题目描述

给你一个区间 $[l, r]$ 和一个正整数 $a$，设 $f(x)$ 表示 $x$ 除 $a$ 的商和余数的和（即 $f(x)=x/a+x\%a$）；

对于 $[l, r]$ 中所有的数 $x$，求 $f(x)$ 的最大值

输入格式

第一行包含一个整数 $t$，表示数据组数；

接下来 $t$ 行，每行包含三个整数 $l_i, r_i, a_i$；

输出格式

对于每组数据，输出一行一个整数，表示 $f(x)$ 的最大值

5
1 4 3
5 8 4
6 10 6
1 1000000000 1000000000
10 12 8

2
4
5
999999999
5

数据范围与提示

【样例 1 解释】 区间为 $[1, 4]$，$a$ 为 $3$，逐一计算：

• $1 / 3 + 1 \% 3 = 1$
• $2 / 3 + 2 \% 3 = 2$
• $3 / 3 + 3 \% 3 = 1$
• $4 / 3 + 4 \% 3 = 2$
• 所以 $f(x)$ 的最大值是 $2$

【数据范围】

• $1 \leq t \leq 10^4$，
• $1 \leq l_i \leq r_i \leq 10^9$，
• $1 \leq a_i \leq 10^9$。