#include <iostream>
#include <vector>
#include <cmath>
#include <list>
#include <map>
#include <algorithm>
#include <climits>
#include <iomanip>
#include <cstdio>
#include <bitset>
#include <cstring>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <string>
using namespace std;
#define ll long long int
#define cbit __builtin_popcountll
#define pl pair<long, long>
#define pqp priority_queue<pl>
// getline(cin, str);  __gcd(a,b)
// vec.insert(vec.begin()+i,value); log2(n); tolower(s[i]);
// ostringstream s; s<<i; string ans =s.str();
// string c=to_string(i);   s.push_back(c);
// next_permutation(nums.begin(),nums.end())
// priority_queue<PII, vector<PII>, greater<PII>> pq;
/* Iterative Function to calculate (x^y)%p
in O(log y) */
unsigned long long power(unsigned long long x, int y, int p)
{
    unsigned long long res = 1; // Initialize result

    x = x % p; // Update x if it is more than or
    // equal to p

    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;

        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}
bool cmp(pair<string, int> &a, pair<string, int> &b)
{
    return a.second < b.second;
}
void sort(map<string, int> &M)
{

    // Declare vector of pairs
    vector<pair<string, int> > A;

    // Copy key-value pair from Map
    // to vector of pairs
    for (auto &it : M)
    {
        A.push_back(it);
    }

    // Sort using comparator function
    sort(A.begin(), A.end(), cmp);

    // Print the sorted value
    for (auto &it : A)
    {

        cout << it.first << ' '
             << it.second << endl;
    }
}
// Returns n^(-1) mod p
unsigned long long modInverse(unsigned long long n, int p)
{
    return power(n, p - 2, p);
}

// Returns nCr % p using Fermat's little
// theorem.
unsigned long long nCrModPFermat(unsigned long long n, int r, int p)
{
    // If n<r, then nCr should return 0
    if (n < r)
        return 0;
    // Base case
    if (r == 0)
        return 1;

    // Fill factorial array so that we
    // can find all factorial of r, n
    // and n-r
    unsigned long long fac[n + 1];
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = (fac[i - 1] * i) % p;

    return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p;
}
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;
}

bool isPrime(ll n)
{
    // Corner cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;

    // This is checked so that we can skip
    // middle five numbers in below loop
    if (n % 2 == 0 || n % 3 == 0)
        return false;

    for (ll i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;

    return true;
}
ll find(ll s, ll n, ll pos)
{
    ll mid = s + n / 2;
    if (mid == pos)
    {
        return 1;
    }
    else if (mid > pos)
    {
        return 1 + find(mid + 1, n, pos);
    }
    else
    {
        return 1 + find(s, mid, pos);
    }
}
ll fact(ll n)
{
    // single line to find factorial
    return (n == 1 || n == 0) ? 1 : n * fact(n - 1);
}
ll num(ll n, ll ans)
{
    n /= 10;
    if (n == 0)
    {
        return ans;
    }
    else
    {
        return ans + num(n, ans + 1);
    }
}
ll nof(ll n)
{
    if (n == 1)
    {
        return 1;
    }
    ll ans = 2;
    for (ll i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            if (i * i != n)
            {
                ans += 2;
            }
            else
            {
                ans++;
            }
        }
    }
    return ans;
}
ll getsum(ll n)
{
    ll ans = 0;
    while (n)
    {
        ans += n % 10;
        n /= 10;
    }
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    // #endif
    // priority_queue<pl> p;
    // bool del[500001]={0};
    // ll i=0;

    ll t = 1;
    cin >> t;
    while (t--)
    {
        ll n,m;
        cin>>n>>m;
        if(n%m==0)
        {
            cout<<1<<"\n";
        }
        else if(n>m)
        {
            cout<<2<<"\n";
        }
        else if(n==m)
        {
            cout<<1<<"\n";
        }
        else{
            if(m%n==0)
            {
                cout<<m/n<<"\n";
            }
            else{
                cout<<m/n +1<<"\n";
            }
        }
    }

    return 0;
}
### Prompt

Create a solution in cpp for the following problem:

You are given two integers n and k.

You should create an array of n positive integers a_1, a_2, ..., a_n such that the sum (a_1 + a_2 + ... + a_n) is divisible by k and maximum element in a is minimum possible.

What is the minimum possible maximum element in a?

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases.

The first and only line of each test case contains two integers n and k (1 ≤ n ≤ 10^9; 1 ≤ k ≤ 10^9).

Output

For each test case, print one integer — the minimum possible maximum element in array a such that the sum (a_1 + ... + a_n) is divisible by k. 

Example

Input


4
1 5
4 3
8 8
8 17


Output


5
2
1
3

Note

In the first test case n = 1, so the array consists of one element a_1 and if we make a_1 = 5 it will be divisible by k = 5 and the minimum possible.

In the second test case, we can create array a = [1, 2, 1, 2]. The sum is divisible by k = 3 and the maximum is equal to 2.

In the third test case, we can create array a = [1, 1, 1, 1, 1, 1, 1, 1]. The sum is divisible by k = 8 and the maximum is equal to 1.

### Response

```cpp
#include <iostream>
#include <vector>
#include <cmath>
#include <list>
#include <map>
#include <algorithm>
#include <climits>
#include <iomanip>
#include <cstdio>
#include <bitset>
#include <cstring>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <string>
using namespace std;
#define ll long long int
#define cbit __builtin_popcountll
#define pl pair<long, long>
#define pqp priority_queue<pl>
// getline(cin, str);  __gcd(a,b)
// vec.insert(vec.begin()+i,value); log2(n); tolower(s[i]);
// ostringstream s; s<<i; string ans =s.str();
// string c=to_string(i);   s.push_back(c);
// next_permutation(nums.begin(),nums.end())
// priority_queue<PII, vector<PII>, greater<PII>> pq;
/* Iterative Function to calculate (x^y)%p
in O(log y) */
unsigned long long power(unsigned long long x, int y, int p)
{
    unsigned long long res = 1; // Initialize result

    x = x % p; // Update x if it is more than or
    // equal to p

    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;

        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}
bool cmp(pair<string, int> &a, pair<string, int> &b)
{
    return a.second < b.second;
}
void sort(map<string, int> &M)
{

    // Declare vector of pairs
    vector<pair<string, int> > A;

    // Copy key-value pair from Map
    // to vector of pairs
    for (auto &it : M)
    {
        A.push_back(it);
    }

    // Sort using comparator function
    sort(A.begin(), A.end(), cmp);

    // Print the sorted value
    for (auto &it : A)
    {

        cout << it.first << ' '
             << it.second << endl;
    }
}
// Returns n^(-1) mod p
unsigned long long modInverse(unsigned long long n, int p)
{
    return power(n, p - 2, p);
}

// Returns nCr % p using Fermat's little
// theorem.
unsigned long long nCrModPFermat(unsigned long long n, int r, int p)
{
    // If n<r, then nCr should return 0
    if (n < r)
        return 0;
    // Base case
    if (r == 0)
        return 1;

    // Fill factorial array so that we
    // can find all factorial of r, n
    // and n-r
    unsigned long long fac[n + 1];
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = (fac[i - 1] * i) % p;

    return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p;
}
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;
}

bool isPrime(ll n)
{
    // Corner cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;

    // This is checked so that we can skip
    // middle five numbers in below loop
    if (n % 2 == 0 || n % 3 == 0)
        return false;

    for (ll i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;

    return true;
}
ll find(ll s, ll n, ll pos)
{
    ll mid = s + n / 2;
    if (mid == pos)
    {
        return 1;
    }
    else if (mid > pos)
    {
        return 1 + find(mid + 1, n, pos);
    }
    else
    {
        return 1 + find(s, mid, pos);
    }
}
ll fact(ll n)
{
    // single line to find factorial
    return (n == 1 || n == 0) ? 1 : n * fact(n - 1);
}
ll num(ll n, ll ans)
{
    n /= 10;
    if (n == 0)
    {
        return ans;
    }
    else
    {
        return ans + num(n, ans + 1);
    }
}
ll nof(ll n)
{
    if (n == 1)
    {
        return 1;
    }
    ll ans = 2;
    for (ll i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            if (i * i != n)
            {
                ans += 2;
            }
            else
            {
                ans++;
            }
        }
    }
    return ans;
}
ll getsum(ll n)
{
    ll ans = 0;
    while (n)
    {
        ans += n % 10;
        n /= 10;
    }
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    // #endif
    // priority_queue<pl> p;
    // bool del[500001]={0};
    // ll i=0;

    ll t = 1;
    cin >> t;
    while (t--)
    {
        ll n,m;
        cin>>n>>m;
        if(n%m==0)
        {
            cout<<1<<"\n";
        }
        else if(n>m)
        {
            cout<<2<<"\n";
        }
        else if(n==m)
        {
            cout<<1<<"\n";
        }
        else{
            if(m%n==0)
            {
                cout<<m/n<<"\n";
            }
            else{
                cout<<m/n +1<<"\n";
            }
        }
    }

    return 0;
}
```