Kaing Calendar

An archaeological expedition recently discovered that the Inca Empire of South America was founded upon the Kaing Empire, a civilization of remarkable achievement. The people of the Kaing Empire are known to have used an unusual calendar. Using two natural numbers $x$ and $y$ that are at most $M$ and $N$ respectively, they wrote each year in the form $\langle x{:}y \rangle$.

The very first year of the world is written as $\langle 1{:}1 \rangle$ and the second year as $\langle 2{:}2 \rangle$. If a given year is $\langle x{:}y \rangle$, the next year $\langle x'{:}y' \rangle$ is determined as follows.

• If $x < M$ then $x' = x + 1$; otherwise $x' = 1$.
• If $y < N$ then $y' = y + 1$; otherwise $y' = 1$.

$\langle M{:}N \rangle$ is the last year of this calendar, and legend says the world ends in that year.

For example, if $M = 10$ and $N = 12$, then the 1st year is $\langle 1{:}1 \rangle$, the 11th year is $\langle 1{:}11 \rangle$, the 13th year is $\langle 3{:}1 \rangle$, and the last (60th) year is $\langle 10{:}12 \rangle$.

Given four integers $M$, $N$, $x$, and $y$, where $\langle M{:}N \rangle$ is the last year of the Kaing calendar, write a program that determines which year $\langle x{:}y \rangle$ represents.

Input is given on standard input. The first line contains an integer $T$, the number of test cases. Each of the following lines contains four integers $M$, $N$, $x$, and $y$. ($1 \le M, N \le 40{,}000$, $1 \le x \le M$, $1 \le y \le N$) Here $\langle M{:}N \rangle$ denotes the last year of the Kaing calendar.

For each test case, print on its own line the integer $k$ such that $\langle x{:}y \rangle$ represents the $k$-th year. If no year is represented by $\langle x{:}y \rangle$ — that is, if $\langle x{:}y \rangle$ is an invalid representation — print $-1$.