该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有$\red{q}$个询问，第$\red{i}$次询问会给出$\red{l_i,r_i,d_i，}$求出最小的正整数$\red{x_i，}$使得其被$\red{d_i}$整除且不属于区间$\red{[l_i,r_i]}$。$\red{x}$属于$\red{[l,r]}$当前仅当$\red{l<=x<=r}$

输入格式

第一行,$\red{1}$个整数$\red{q}$

接下来$\red{q}$行，第$\red{i}$行包括$\red{l_i,r_i,d_i}$

输出格式

每行一个整数，表示最小的正整数$\red{x_i，}$使得其被$\red{d_i}$整除且不属于区间$\red{[l_i,r_i]}$

样例

输入样例

5
2 4 2
5 10 4
3 10 1
1 2 3
4 6 5

输出样例

6
4
1
3
10

提示

对于$\red{50\%}$数据，$\red{1<=l_i,r_i,d_i<=10^3}$；

对于$\red{100\%}$数据，$\red{1<=l_i,r_i<=10^9,1<=d_i<=10^9,1<=q<=500}$。