프로베니우스 문제

프로베니우스 문제는 독일 수학자 G. 프로베니우스(1849-1917)의 이름을 딴 오래된 수학 문제다.

1보다 큰 정수 $a_1, a_2, \ldots, a_n$의 최대공약수가 1이라고 하자. 이때 $w_i \ge 0$인 정수 계수로 $w_1 a_1 + w_2 a_2 + \cdots + w_n a_n$ 꼴로 나타낼 수 없는 0 이상의 정수는 유한개뿐이라는 사실이 알려져 있다. 그중 가장 큰 수를 $a_1, a_2, \ldots, a_n$의 프로베니우스 수라 부르고 $F(a_1, a_2, \ldots, a_n)$으로 쓴다. 즉 $F(a_1, a_2, \ldots, a_n)$은 $a_1, a_2, \ldots, a_n$의 음이 아닌 정수 계수 선형결합으로 나타낼 수 없는 가장 큰 0 이상의 정수다.

$n = 2$이면 $F(a_1, a_2)$를 주는 간단한 공식이 있다. 그러나 $n \ge 3$부터는 훨씬 복잡해진다. $n = 3$일 때는 $a_1, a_2, a_3$이 특별한 값일 때만 공식이 알려져 있고, $n > 4$에 대해서는 공식이 전혀 알려져 있지 않다.

여기서는 $n = 4$인 경우를 다룬다. $a, b, c, d > 1$이고 $\gcd(a, b, c, d) = 1$인 네 정수 $a, b, c, d$가 주어질 때 다음 두 가지를 구한다.

• 1,000,000 이하의 0 이상 정수 가운데 $a, b, c, d$의 음이 아닌 정수 계수 선형결합으로 나타낼 수 없는 수는 몇 개인가?
• $a, b, c, d$의 프로베니우스 수가 1,000,000 이하인가? 이하라면 그 값은 얼마인가?

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

• 한 줄에 네 정수 $a, b, c, d$가 공백 하나로 구분되어 주어진다. ($1 < a, b, c, d \le 10000$, $\gcd(a, b, c, d) = 1$)

각 테스트 케이스마다 두 줄을 출력한다.

• 첫째 줄에는 0 이상 1,000,000 이하(양 끝 포함)인 정수 가운데 음이 아닌 정수 $w, x, y, z$로 $a \cdot w + b \cdot x + c \cdot y + d \cdot z$와 같이 나타낼 수 없는 수의 개수를 출력한다.
• 둘째 줄에는 프로베니우스 수가 1,000,000 이하이면 그 값을, 1,000,000보다 크면 -1을 출력한다.