Majestic Numbers

Input

The first line consists of a single integer $t$ ( $1 \leq t \leq 2 \cdot 1 0^{5}$ 1 \le t \le 2 \cdot 10^5) $-$ the number of testcases.

Each testcase consists of three integers $l, r$ and $x$ ( $2 \leq x \leq 1 0^{9}$ 2 \le x \le 10^9 , $1 \leq l \leq r \leq 1 0^{9}$ 1 \le l \le r \le 10^9).

Output

The output consists of $t$ lines, each containing one value (the number with the maximum majesticness in the range $(l, r)$ (l,r), if multiple numbers satisfy the condition output the maximum one).

Examples

Example 1

Loading

Scoring

Subtask $1$ ( $125$ points): No additional constraints