Shepherds and Engineers

Westmoreland is a peaceful country of quiet rivers, rough moors, and shepherds who herd their flocks. To reach the town's sheep market a shepherd must cross rivers. After heavy rainfall wading became too dangerous, so engineers built bridges and were allowed to charge a toll, paid in sheep, on every shepherd who crosses.

To stop excessive tolls the king decreed that whenever a shepherd crosses a bridge with some sheep and the engineer takes a toll:

1. what the shepherd keeps must be strictly more than what the engineer takes, and
2. what the shepherd keeps must be an integral multiple of what the engineer takes.

The engineer always charges the largest toll these rules allow. So if the shepherd arrives at a bridge with $n$ sheep and pays a toll of $t$ sheep, the kept sheep $n - t$ must satisfy $n - t = k\cdot t$ for some integer $k \ge 2$; equivalently $n = (k+1),t$ with $k+1 \ge 3$. Among all valid tolls the engineer takes the maximum $t$. If no valid toll exists (for example when the shepherd has only one or two sheep) the crossing is free.

Shepherds fight back by giving away sheep to local shepherds before a bridge, lowering their count to a number with a smaller maximum toll. For example, a shepherd who must sell $40$ sheep four bridges from town can start with $47$ sheep:

• Bridge 1: $47$ sheep, toll $1$, keep $46$.
• Bridge 2: $46$ sheep, toll $2$, keep $44$.
• Bridge 3: instead of paying the toll $11$ on $44$, give away $1$ sheep, cross with $43$, toll $1$, keep $42$.
• Bridge 4: give away $1$ sheep, cross with $41$, toll $1$, keep $40$.

He enters town with exactly $40$ sheep, and no smaller starting number works.

Given the number $s$ of sheep a shepherd wants to bring into town and the number $b$ of bridges on the way, find the minimum number of sheep he must start his journey with. Note that the best plan may sometimes leave him entering town with more sheep than required.

The first line contains a single integer $T$: the number of test cases.

Each test case is a single line with two integers $s$ and $b$:

• $s$ ($0 < s \le 10^6$) — the number of sheep that must enter the town,
• $b$ ($0 \le b \le 1000$) — the number of bridges to cross.

For each test case, print a single line with one integer: the minimum number of sheep the shepherd must start with.