34186번 - 17마리 낙타

문제

상인이 임종 전 세 아들에게 유언을 남겼다.

"내가 17ドル$마리의 낙타를 물려줄 터이니 첫째는 $\frac 1 {2}$을 갖고 둘째는 $\frac 1 {3}$을 갖고 셋째는 $\frac 1 {9}$을 갖거라."

삼형제는 심히 난감한 상황에 처했는데 17ドル$은 2ドル$로 나누어 떨어지지 않고 3ドル$이나 9ドル$로 나누어 떨어지지도 않기 때문이었다. 하지만 현명한 나그네가 나타나 낙타 1ドル$마리를 빌려주자, 세 아들은 각자 9ドル$마리, 6ドル$마리, 2ドル$마리씩 나누어 가질 수 있었다. 그러자 삼형제가 가진 낙타의 수의 총합은 원래 상인이 가지고 있던 17ドル$마리가 되었고, 나그네는 다시 자신의 낙타 1ドル$마리를 돌려받았다.

삼형제는 상인의 두 번째 유언도 확인해 보았다.

"내가 12ドル$마리 양을 물려줄 터이니 첫째는 $\frac 1 {4}$을 갖고 둘째는 $\frac 1 {4}$을 갖고 셋째는 $\frac 1 {4}$을 갖거라."

이번에는 12ドル$가 4ドル$로 나누어 떨어지기 때문에 각각 3ドル$마리씩 나누어 가질 수 있었지만, 양 3ドル$마리가 남는 것이 마음에 들지 않았던 첫째는 나그네를 다시 불렀다. 이번에는 나그네가 양 4ドル$마리를 빌려주어 전체가 16ドル$마리가 되었다. 그러자 첫째, 둘째, 셋째 모두 16ドル$의 $\frac 1 {4}$인 4ドル$마리를 가져 상인의 양을 남김없이 나누어 가질 수 있었고, 나그네는 다시 자신의 양 4ドル$마리를 돌려받았다.

여전히 상인이 세 아들에게 남긴 유언이 $T$개 남아 있었다. 각 유언은 아래와 같았다.

"내가 $N$마리 가축을 물려줄 터이니 첫째는 $\frac 1 {A}$을 갖고 둘째는 $\frac 1 {B}$을 갖고 셋째는 $\frac 1 {C}$을 갖거라."

하지만 나그네가 떠난 뒤였기에 첫째는 여러분에게 도움을 요청했다. 여러분은 $K$마리의 가축을 빌려주어 첫째, 둘째, 셋째가 $N+K$마리의 각각 $\frac 1 {A},ドル $\frac 1 {B},ドル $\frac 1 {C}$를 가지도록 도와줄 것이다. 단, 삼형제가 가진 가축의 수의 합이 정확히 $N$이 되어 여러분은 빌려준 만큼인 $K$마리의 가축을 돌려받아야 한다. 이때 첫째, 둘째, 셋째가 가진 낙타의 수는 각각 정수여야 한다.

삼형제에게 빌려주어야 하는 가축의 수 $K$의 최솟값을 구해보자. $K$는 음이 아닌 정수이다.

입력

첫째 줄에 상인이 남긴 유언의 수 $T$가 주어진다. (1ドル \le T \le 1,000円$)

둘째 줄부터 $T$개 줄에 걸쳐 각 유언에 나타난 정수 $N,ドル $A,ドル $B,ドル $C$가 주어진다. (1ドル \le N \le 10^6$; 2ドル \le A, B, C \le 10^4$)

출력

$T$개 줄에 걸쳐 각 유언에 대해 빌려주어야 하는 가축의 수 $K$의 최솟값을 출력한다. 단, 여러분이 빌려주지 않아도 문제를 해결할 수 있다면 0ドル$을 출력하고, 여러분이 가축을 아무리 많이 빌려주더라도 유언에 따라 삼형제가 문제를 해결할 수 없다면 $-1$을 출력한다.

제한

힌트