题目描述

三年级七班共有 $n$ 名同学。体育课开始，他们从左到右站成了一排，准备进行报数分组。

体育老师口袋里有很多袋装的糖果（一个袋子里有很多糖果），他准备在分组的过程中顺便将这些袋装糖果分给同学们。

具体地，在从左到右报数的过程中，每报数 $k$ 名同学，体育老师就会将这 $k$ 名同学划为一组，同时给予这 $k$ 名同学中的最后一名一袋糖果，让这最后一名同学来负责分发给组内的同学。也就是说，体育老师会依次给从左到右第 $k,2k,\cdots$ 名同学一袋糖果。

恰巧，三年级六班的同学听到了三年级七班发糖果的消息，于是他们打算混入队伍的末尾（即队伍最右侧），企图白嫖到一袋糖果。

三年级六班的同学想知道，他们至少需要向队伍末尾混入多少人

输入格式

第一行一个正整数$T$，表示有 $T$组数据

接下来$T$行，每行两个整数 $n, k$

输出格式

$T$行，每行一个整数，表示答案

样例

1
10 3

2

1
16 4

4

提示

样例 1 解释

此时每 $3$ 人分一组。三年级六班只需要向队伍中混入 $2$ 名同学，就可以和原来三年级七班的最后 $1$ 名同学一同凑成一组。

由于混入的这 $2$ 名同学在队伍的末尾，因此这一组中的最后一名同学一定是隔壁班的同学，因此隔壁班的同学可以白嫖到一袋糖果。

样例 2 解释

此时每 $4$ 人分一组。三年级七班的所有同学都已经分好了组，因此三年级六班需要完整地向队伍中混入 $4$ 名同学凑成一组，才能白嫖到一袋糖果。

数据范围

对于 $100\%$ 的数据，$1 \leq n \leq 10 ^ {9}$，$2 \leq k \leq 10 ^ 9$，$T\leq 20$。