#include <bits/stdc++.h>

using namespace std;

#define ll     long long
#define fr     first
#define sec    second
#define rep(i,n)  for(i=0;i<n;i++)
#define vi     vector <int>
#define vc     vector <char>
#define vl     vector <ll>
#define vb     vector <bool>
#define pb     push_back
#define M      1000000007
#define ios    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define open   freopen("input.txt","r",stdin);
#define close  freopen("output.txt","w",stdout);
#define M_PI   3.14159265358979323846
#define ppi    pair<int, int>
#define ppl    pair<ll, ll>
#define nn     100003
#define MM     1000000007
#define MN     1000005
#define MAX    998244353

ll spf[MN];

pair <ll,ll> intersect(pair <ll,ll> range, pair <ll,ll> range_1)
{
    return make_pair(max(range.fr, range_1.fr), min(range.sec, range_1.sec));
}

bool sortby(ppl p,ppl q)
{
    if(p.sec==q.sec)
        return p.fr>q.fr;
    return p.sec<q.sec;
}

void sieve() 
{ 
    spf[1] = 1; 
    for (ll i = 2; i < MN; i++) 
        spf[i] = i; 
        
    for (ll i = 4; i < MN; i+=2) 
        spf[i] = 2; 
  
    for (ll i=3; i*i < MN; i++) 
    {
        if (spf[i] == i) 
        { 
            for (ll j = i*i; j < MN; j+=i) 
                if (spf[j]==j) 
                    spf[j] = i; 
        } 
    } 
} 

vl getFactorization(ll x) 
{ 
    vl ans;
    set <ll> s;
    ans.pb(1);
    ans.pb(x);
    while (x != 1) 
    {
        if(s.find(spf[x]) == s.end())
        {
            ans.pb(spf[x]); 
            s.insert(spf[x]);
        }
        x = x / spf[x]; 
    } 
    sort(ans.begin(),ans.end());
    return ans;
} 

bool prime(ll x)
{
    if(spf[x] == x)
        return true;
    return false;
}

vl subarraySum(vector<ppl> v, ll m) 
{
    ll i;
    unordered_map<ll, pair<ll,ppl>> prevSum; 
    vl res(2); 
    ll n=v.size();
    ll currsum = 0; 
    rep(i,n)
    { 
        currsum += v[i].fr; 
        if (currsum == m)  
        {
            res[0]=0;
            res[1]=i;
            return res;
        }             
        if (prevSum.find(currsum - m) != prevSum.end())  
        {
            res[0] = prevSum[currsum - m].sec.sec; 
            res[1] = i;
            return res;
        }
        else
        {
            prevSum[currsum].fr=0;
            prevSum[currsum].sec={0,i};
        }
    } 
    res[0]=-1;
    res[1]=-1;
    return res; 
}

// function to find gcd of 2 numbers - uses Euclid's algo
int find_gcd (int a, int b)
{
    if(a == 0)
        return b;
    return find_gcd(b % a, a);
}

void compute(ll a, ll b, vl &res)
{
    ll i; 
    res[0] = 0;
    for(i=1;i<=a*b;i++)
    {
        res[i] = res[i-1];
        if(i%a%b != i%b%a)
            res[i] += 1;
    }
    return;
}

void solve()
{
    ll n,k;
    cin>>n>>k;
    if(n==k)
        cout<<"1\n";
    else if(n==1)
        cout<<k<<"\n";
    else if(n<k)
    {
        cout<<k/n+(k%n?1:0)<<"\n";
    }
    else
    {
        if(n%k==0)
            cout<<"1\n";
        else
        {
            ll temp = n;
            n = (n/k+1)*k;
            ll ans = n/temp+(n%temp?1:0);
            cout<<ans<<"\n";
        }
    }
    return;
}

int main()
{
    ios;
    /*#ifndef ONLINE_JUDGE    
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif*/
    ll t;
    cin>>t;
    // sieve();
    while(t--)
        solve();
    return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

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 <bits/stdc++.h>

using namespace std;

#define ll     long long
#define fr     first
#define sec    second
#define rep(i,n)  for(i=0;i<n;i++)
#define vi     vector <int>
#define vc     vector <char>
#define vl     vector <ll>
#define vb     vector <bool>
#define pb     push_back
#define M      1000000007
#define ios    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define open   freopen("input.txt","r",stdin);
#define close  freopen("output.txt","w",stdout);
#define M_PI   3.14159265358979323846
#define ppi    pair<int, int>
#define ppl    pair<ll, ll>
#define nn     100003
#define MM     1000000007
#define MN     1000005
#define MAX    998244353

ll spf[MN];

pair <ll,ll> intersect(pair <ll,ll> range, pair <ll,ll> range_1)
{
    return make_pair(max(range.fr, range_1.fr), min(range.sec, range_1.sec));
}

bool sortby(ppl p,ppl q)
{
    if(p.sec==q.sec)
        return p.fr>q.fr;
    return p.sec<q.sec;
}

void sieve() 
{ 
    spf[1] = 1; 
    for (ll i = 2; i < MN; i++) 
        spf[i] = i; 
        
    for (ll i = 4; i < MN; i+=2) 
        spf[i] = 2; 
  
    for (ll i=3; i*i < MN; i++) 
    {
        if (spf[i] == i) 
        { 
            for (ll j = i*i; j < MN; j+=i) 
                if (spf[j]==j) 
                    spf[j] = i; 
        } 
    } 
} 

vl getFactorization(ll x) 
{ 
    vl ans;
    set <ll> s;
    ans.pb(1);
    ans.pb(x);
    while (x != 1) 
    {
        if(s.find(spf[x]) == s.end())
        {
            ans.pb(spf[x]); 
            s.insert(spf[x]);
        }
        x = x / spf[x]; 
    } 
    sort(ans.begin(),ans.end());
    return ans;
} 

bool prime(ll x)
{
    if(spf[x] == x)
        return true;
    return false;
}

vl subarraySum(vector<ppl> v, ll m) 
{
    ll i;
    unordered_map<ll, pair<ll,ppl>> prevSum; 
    vl res(2); 
    ll n=v.size();
    ll currsum = 0; 
    rep(i,n)
    { 
        currsum += v[i].fr; 
        if (currsum == m)  
        {
            res[0]=0;
            res[1]=i;
            return res;
        }             
        if (prevSum.find(currsum - m) != prevSum.end())  
        {
            res[0] = prevSum[currsum - m].sec.sec; 
            res[1] = i;
            return res;
        }
        else
        {
            prevSum[currsum].fr=0;
            prevSum[currsum].sec={0,i};
        }
    } 
    res[0]=-1;
    res[1]=-1;
    return res; 
}

// function to find gcd of 2 numbers - uses Euclid's algo
int find_gcd (int a, int b)
{
    if(a == 0)
        return b;
    return find_gcd(b % a, a);
}

void compute(ll a, ll b, vl &res)
{
    ll i; 
    res[0] = 0;
    for(i=1;i<=a*b;i++)
    {
        res[i] = res[i-1];
        if(i%a%b != i%b%a)
            res[i] += 1;
    }
    return;
}

void solve()
{
    ll n,k;
    cin>>n>>k;
    if(n==k)
        cout<<"1\n";
    else if(n==1)
        cout<<k<<"\n";
    else if(n<k)
    {
        cout<<k/n+(k%n?1:0)<<"\n";
    }
    else
    {
        if(n%k==0)
            cout<<"1\n";
        else
        {
            ll temp = n;
            n = (n/k+1)*k;
            ll ans = n/temp+(n%temp?1:0);
            cout<<ans<<"\n";
        }
    }
    return;
}

int main()
{
    ios;
    /*#ifndef ONLINE_JUDGE    
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif*/
    ll t;
    cin>>t;
    // sieve();
    while(t--)
        solve();
    return 0;
}

```