您将收到以下形式的 $$$q$$$ 查询:
给定三个整数$$$l_i$$$、$$$r_i$$$和$$$d_i$$$,找到最小正整数$$$x_i$$$,使其能被$$$d_i$$$整除,并且不属于段$$$[l_i, r_i]$$$。
你能回答所有问题吗?
回想一下,如果 $$$l \le x \le r$$$,则数字 $$$x$$$ 属于段 $$$[l, r]$$$。
输入
第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 500$$$) — 查询数量。
接下来是 $$$q$$$ 行,每行包含一个以 $$$l_i$$$ $$$r_i$$$ $$$d_i$$$ ($$$1 \le l_i \le r_i \le 10^9$$$, $$$1 \le d_i \le 10^9$$$) 格式给出的查询。 $$$l_i$$$、$$$r_i$$$ 和 $$$d_i$$$ 是整数。
输出
对于每个查询打印一个整数:该查询的答案。
示例
输入 #1
5 2 4 2 5 10 4 3 10 1 1 2 3 4 6 5
输出 #1
6 4 1 3 10