The Frobenius Problem

The Frobenius problem is an old problem in mathematics, named after the German mathematician G. Frobenius (1849-1917).

Let $a_1, a_2, \ldots, a_n$ be integers larger than 1 whose greatest common divisor is 1. It is known that only finitely many integers greater than or equal to 0 cannot be written as $w_1 a_1 + w_2 a_2 + \cdots + w_n a_n$ with integer coefficients $w_i \ge 0$. The largest such integer is the Frobenius number of $a_1, a_2, \ldots, a_n$, written $F(a_1, a_2, \ldots, a_n)$. So $F(a_1, a_2, \ldots, a_n)$ is the largest nonnegative integer that is not a nonnegative integer linear combination of $a_1, a_2, \ldots, a_n$.

For $n = 2$ there is a simple formula for $F(a_1, a_2)$. For $n \ge 3$ it is much more complicated. When $n = 3$, formulas are known only for special choices of $a_1, a_2, a_3$, and for $n > 4$ no formula is known at all.

This problem asks about the case $n = 4$. Four integers $a, b, c, d$ are given with $a, b, c, d > 1$ and $\gcd(a, b, c, d) = 1$. Two things are asked.

• How many nonnegative integers less than or equal to 1,000,000 cannot be written as a nonnegative integer linear combination of $a$, $b$, $c$ and $d$?
• Is the Frobenius number of $a, b, c, d$ less than or equal to 1,000,000, and if it is, what is its value?

The first line contains the number of test cases. Each test case has the following format.

• One line with four integers $a, b, c, d$ separated by single spaces ($1 < a, b, c, d \le 10000$ and $\gcd(a, b, c, d) = 1$).

Print two lines for every test case.

• The first line contains the number of integers between 0 and 1,000,000 (both included) that cannot be written as $a \cdot w + b \cdot x + c \cdot y + d \cdot z$ with nonnegative integers $w, x, y, z$.
• The second line contains the Frobenius number if it is less than or equal to 1,000,000, and -1 otherwise.