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$.