No testdata at current.

Background

今天，你坐上时光机，来到了唐朝。你来到了唐朝的集市上，看到一个人在卖冰糖葫芦，你走了过去，想尝尝唐朝的冰糖葫芦是什么味道。可惜你没有唐朝通用货币。那个小贩看出来了你没有钱，笑了笑，说：“年轻人，只要你能回答出我的问题，我就免费给你一串冰糖葫芦。”你为了能吃到冰糖葫芦，欣然接受了挑战。

Description

小贩说：“一个袋子里有a颗山楂，做一串冰糖葫芦需要b颗山楂。请问我至少需要几袋山楂(不能拆袋)，才能完整的穿完若干串冰糖葫芦后，恰好剩下1颗山楂呢？”

Format

Input

多组数据。 第一行一个整数t $(1≤t≤100)$。 后面t行，每行两个整数a，b，分别表示一个袋子里有a颗山楂，一串冰糖葫芦需要b个山楂。每次询问相互独立。

Output

t行，每行一个整数，表示小贩想要的答案。保证一定有解（其实就是gcd(a,b)=1）。

Samples

4
5 7
7 51
4343434 5656567
5656567 4343434

3
22
4260790
1071757

Limitation

• $5*3 \ Mod \ 7 \ = \ 1$
• $7*22 \ Mod \ 51 \ = \ 1$
• 对于100%的数据，$2≤a,b≤10^{9}$
• 有40%的数据，保证 $b是质数$