Minimum Number of Pizzas

 Chef is throwing a party for his 

N$N$ friends. There is a pizza store nearby and he wants to buy pizza for his friends. Each pizza has exactly K$K$ slices. Chef's friends get sad if one gets more slices than the other. Also, Chef gets sad if there are some pizza slices left. More formally, suppose Chef buys P$P$ pizzas, then everyone is happy if and only if there is a way to distribute K⋅P$K\cdot P$ slices between N$N$ friends.

You need to find the minimum number of pizzas Chef has to buy to share all the slices among his friends so that none of his friends gets sad. Note that Chef hates pizza and doesn't take any slices.

Input Format

• First line of input contains T$T$, the number of test cases. Then the test cases follow.
• Each test case contains two space-separated integers N$N$ and K$K$, where N$N$ is the number of friends of chef and K$K$ is the number of slices in a pizza.

Output Format

For each test case, print the minimum number of pizzas chef has to buy to share among his friends so that none of his friends gets sad.

Constraints

• 1≤T≤2⋅105$1\le T\le 2\cdot {10}^5$
• 1≤N,K≤109$1\le N,K\le {10}^9$

Subtasks

• Subtask 1 (100 points): Original constraints

Sample Input 1 

3
2 2
2 3
4 2

Sample Output 1 

1
2
2

Explanation

• Test case 1$1$: One pizza has 2$2$ slices. And there are 2$2$ friends. So chef can just buy one pizza and give one slice to one friend and another slice to another friend.
• Test case 2$2$: One pizza has 3$3$ slices. And there are 2$2$ friends. So chef can't share one pizza without being left out with a slice. So he needs to buy at least 2$2$ pizzas. And if he buys 2$2$ pizzas, he can give 3$3$ slices to one friend and 3$3$ to another. So the minimum number of pizzas chef needs to buy is equal to 2$2$.
• Test case 3$3$: One pizza has 2$2$ slices. And there are 4$4$ friends. So chef can't share one pizza among the 4$4$ friends. So he needs to buy at least 2$2$ pizzas. And if he buys 2$2$ pizzas, he can give 1$1$ slice to each of his friends. So the minimum number of pizzas chef needs to buy is equal to 2$2$.

Code:

#include <iostream>

using namespace std;

long long gcd(long long int a, long long int b)

{

    if (b == 0)

    return a;

    return gcd(b, a % b);

}

long long lcm(int a, int b)

{

    return (a / gcd(a,b))*b;

}

signed main(){

    long long int t;

    cin>>t;

    while(t--)

    {

        long long int n,k;

        cin>>n>>k;

        long long int res=lcm(n,k)/k;

        cout<<res<<"\n";

    }

    return 0;

}