You are given $q$ queries in the following form:

Given three integers $l_i$, $r_i$ and $d_i$, find minimum positive integer $x_i$ such that it is divisible by $d_i$ and it does not belong to the segment $[l_i, r_i]$.

Can you answer all the queries?

Recall that a number $x$ belongs to segment $[l, r]$ if $l \le x \le r$.

Input

The first line contains one integer $q$ ($1 \le q \le 500$) — the number of queries.

Then $q$ lines follow, each containing a query given in the format $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$ and $d_i$ are integers.

Output

For each query print one integer: the answer to this query.

Samples

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

6
4
1
3
10