The only difference between the easy version and the hard version is the constraints.

After solving the easy version, AZOZ with an O needed a harder task, so Basboos gave him the same task, but $x$ in this problem is toooooo large.

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^2$), the number of test cases.

The following $T$ lines each contain two integers, $x$ and $y$ ($1 \leq x \leq 10^{10^5}; 1 \leq 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$.

Yes you are not blind it is 10 to the power of 10 to the power of 5 (ᵔᵕᵔ)