Background

Original problem link: https://oier.team/problems/J1B.

Problem Description

Define $\lfloor X \rfloor$ as the greatest integer less than or equal to $X$. For example, $\lfloor 1.99 \rfloor = 1, \lfloor 7 \rfloor = 7$.

There are five positive integers $n, m, a, b, c$, and it is known that $b = \left\lfloor \frac{a}{n} \right\rfloor$, $c = \left\lfloor \frac{b}{m} \right\rfloor$.

Given the values of $a$ and $c$, find a valid value of $b$, or report that no valid value of $b$ exists.

This problem uses a custom checker. If multiple valid values of $b$ exist, output any one of them.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, the number of test cases.

For each test case, input one line with two positive integers $a, c$.

Output Format

For each test case, output one integer on a single line. If no valid value of $b$ exists, output -1; otherwise output a valid value of $b$.

This problem uses a custom checker. If multiple valid values of $b$ exist, output any one of them.

4
1 1
7 3
23 8
17 23

1
3
-1
-1

Hint

"Sample Explanation #1"

For the first test case, choosing $n = 1, m = 1$ yields $b = 1$.

For the second test case, choosing $n = 2, m = 1$ yields $b = 3$.

For the third and fourth test cases, it can be proven that no valid value of $b$ exists.

Constraints

Special property: It is guaranteed that for each given $a, c$, a valid value of $b$ always exists.

For $100\%$ of the testdata, $1 \leq T \leq 10^5$, $1 \leq a, c \leq 10^{18}$.

July 15, 2024: Added 7 hack testdata cases to Subtask #1.

Translated by ChatGPT 5