For two integers a and c, we define a and a third integer b to be almost factors of c by choosing the minimal b that minimizes |abc|. Your task will be to determine b given a and c.

Input

Your input file will consist of a single integer N, the number of test cases in the file, followed by N pairs of integers a and c. All tokens in the input will be separated by some whitespace.

Output

Your output should consist of N newline-separated integers, each one representing b for the corresponding pair (ac) in the input.

Constraints

5  N – 20
a, – c 1010

Sample input:

5
18 24
77 176
34 144
24 426
273 628

Sample output:

1
2
4
18
2

Code (C++):

//============================================================================
// Name        : almost.cpp
// Author      : Francesco Laurita
// Version     : 1.0
// Copyright   : Francesco Laurita
// Description :
//============================================================================

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
  int ntest, a, c, b;
  cin >> ntest;
  while (ntest--) {
    cin >> a;
    cin >> c;
    b = c / a;
    if (abs((b + 1) * a - c) < abs(b * a - c)) {
      b++;
    }
    cout << b << endl;
  }
  return 0;
}

© 2013 Francesco Laurita' s blog Suffusion theme by Sayontan Sinha