문제
철수는 얼마 전 ‘나머지’연산에 대해 배웠다.
양의 정수 N 을 다른 양의 정수 M 으로 나눈 나머지는 항상 0 이상 M −1 이하의 정수가 된다는 사실이 신기한 철수는 혼자만의 숫자 놀이를 고안했다.
먼저 철수는 양의 정수를 3개 임의로 고른다: X1, X2, X3 다음, 3개의 양의 정수 P1, P2, P3을 고르는데, P1 > X1, P2 > X2, P3 > X3를 만족하도록 고른다.
철수가 알고 싶은 것은 아래의 조건을 만족하는 가장 작은 양의 정수 N 이다.
N 을 P1로 나눈 나머지가 X1 N 을 P2로 나눈 나머지가 X2 N 을 P3로 나눈 나머지가 X3
철수가 선택한 P1, P2, P3, X1, X2, X3가 주어졌을 때, 가장 작은 정수 N 을 찾는 프로그램을 작성하시오.
입력
첫 행에는 테스트 케이스의 수 T(1 ≤ T ≤ 20) 가 주어진다. 테스트 케이스로는 공백으로 구분된 정수 6개가 순서대로 주어진다. P1, P2, P3, X1, X2, X3 순서로 주어진다. 각 정수는 300을 넘지 않는다.
출력
가장 작은 양의 정수 N 을 출력한다. 단, 조건을 만족하는 1,000,000,000미만의 양의 정수가 없을 경우 −1을 출력한다.
예제
3
20 20 20 1 2 3
2 3 5 1 1 1
2 4 8 1 2 3
-1
1
-1
로그인해야 코드를 작성할 수 있어요.