야구 시즌

KOI 야구 리그에는 $ N $개의 지역리그가 존재하고 각 지역리그에는 $ M $개의 팀이 존재해서, 리그 전체로는 $ N \times M $개의 팀으로 운영되고 있다.

한 시즌에 각 팀은 같은 지역리그 팀뿐만 아니라 다른 지역리그 팀과도 경기를 해야 한다. 같은 지역리그 팀과의 팀당 경기 수는 $ A $로 같은 지역리그 팀들에 대해서 모두 동일하다. 즉, 한 팀 $ X $는 같은 지역리그에 있는 모든 팀 $ Y $($ \neq X $)와 각각 $ A $번의 경기를 한다. 또한 다른 지역리그 팀과의 팀당 경기 수는 $ B $로 다른 지역리그 팀들에 대해서 모두 동일하다. 즉, 한 팀 $ X $는 다른 지역리그에 있는 모든 팀 $ Z $($ \neq X $)와 각각 $ B $번의 경기를 한다. 단, $ A $와 $ B $는 $ A=k \times B $ ($ k $는 1 이상의 정수)를 만족해야 한다.

세계적 판데믹의 영향으로 올해 KOI 야구 리그는 시즌을 단축하여, 리그의 전체 경기 수가 $ D $개 이하 이면서 $ D $에 가장 가깝게 되도록 정하기로 했다. 따라서 같은 지역리그 팀과의 팀당 경기 수 $ A $와 다른 지역리그 팀과의 팀당 경기 수 $ B $를 새롭게 결정해야 한다. 물론, $ A=k \times B $를 만족해야 하고, $ k $는 변함없이 유지되어야 한다. 또한 각 팀은 다른 팀과 적어도 한 번이상은 경기를 해야 한다. 다시 말해서, $ A \ge 1 $, $ B \ge 1 $을 만족해야 한다.

예를 들어, $ N=2 $, $ M=3 $, $ k=3 $일 때, 경기 수 제한 $ D=60 $이면, $ A=6 $, $ B=2 $일 때, 다른 지역리그 팀들과의 총 경기 수는 $ 18 $이고, 같은 지역리그 팀들과의 총 경기 수는 $ 36 $이다. 따라서 리그 전체 경기 수는 $ 54 $로 $ D $에 가장 가까운 새로운 경기 수이다.

지역리그의 개수 $ N $, 각 지역리그에 속하는 팀 수 $ M $, 그리고 위에서 $ A=k \times B $를 만족하는 정수 $ k $, 새로운 경기 수 제한 $ D $가 주어질 때, $ D $ 이하이면서 $ D $에 가장 가까운 리그 전체 경기 수를 계산해서 출력하는 프로그램을 작성하시오.

• 주어지는 모든 수는 정수이다.
• 하나의 입력 데이터에서 $ 1 $개 이상 $ 1\,000 $개 이하의 테스트 케이스를 해결해야 한다.
• $ 2 \le N, M \le 100 $
• $ 1 \le k \le 100 $
• $ 1 \le D \le 1\,000\,000\,000 $

1. (5점) $ N=2 $
2. (5점) $ M=2 $
3. (5점) $ k=1 $
4. (85점) 추가 제약 조건 없음

첫 번째 줄에 테스트 케이스의 개수 $ T $가 주어진다.

다음 $ T $개의 줄에 각 테스트 케이스의 정보가 한 줄에 하나씩 주어진다.

각 테스트 케이스는 하나의 줄에 네 개의 정수 $ N $, $ M $, $ k $, $ D $가 공백 하나를 사이로 두고 주어진다.

$ T $개의 각 줄에 각 테스트 케이스에 대해 리그 전체 경기 수를 출력한다.

만약 조건을 만족하는 경기 수가 존재하지 않으면 -1을 출력한다.