#2890. 【入门】糖果

【入门】糖果

题目描述

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

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

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

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

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

输入格式

第一行一个正整数TT,表示有 TT组数据

接下来TT行,每行两个整数 n,kn, k

输出格式

TT行,每行一个整数,表示答案

样例

1
10 3
2
1
16 4
4

提示

样例 1 解释

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

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

样例 2 解释

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

数据范围

对于 100%100\% 的数据,1n1091 \leq n \leq 10 ^ {9}2k1092 \leq k \leq 10 ^ 9T20T\leq 20