该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

小T要过生日了，他准备了n根火腿，他想将这些火腿均分给m位朋友。为了省事，小T想切最少的刀数，使这n根火腿分成均等的m份。请问最少要切几刀？

Input

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

接下来T组数据，每组共一行，有两个数字n，m。

Output

每组数据一行，输出最少要切的刀数。

Samples

2
2 6
6 2

4
0

Limitation

100%的数据保证T<=1000；n,m<=2147483647。