📖 문제 개요

문제

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

"내가 $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$을 출력한다.

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2