Francesco Laurita' s blog

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 |ab-c|. 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 (a, c) in the input.

Constraints

5 ≤ N ≤ 20
1 ≤ a, c ≤ 10¹⁰

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;
}