The only difference between the easy version and the hard version is the constraints.
Basboos decided to challenge AZOZ with an O to a numerical problem. Of course, AZOZ with an O finds it easy to solve. Can you solve it as well?
Given two integers $x$ and $y$, find the smallest possible integer $k$ such that $k \geq x$ and $k$ is divisible by $y$.
The first line of input contains an integer $T$ ($1 \leq T \leq 10^5$), the number of test cases.
The following $T$ lines each contain two integers, $x$ and $y$ ($1 \leq x, y \leq 10^9$).
For each test case, output a single integer $k$, the smallest possible integer such that $k \geq x$ and $k$ is divisible by $y$.
Input | Output |
---|---|
3 24 7 2 10 13 69 Copy
|
28 10 69 Copy
|