야구 시즌

문제

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

한 시즌에 각 팀은 같은 지역리그 팀뿐만 아니라 다른 지역리그 팀과도 경기를 해야 한다. 같은 지역리그 팀과의 팀당 경기 수는 $AA$로 같은 지역리그 팀들에 대해서 모두 동일하다. 즉, 한 팀 $XX$는 같은 지역리그에 있는 모든 팀 $YY$ ($\mathrm{\ne }X\backslash ne\; X$)와 각각 $AA$번의 경기를 한다. 또한 다른 지역리그 팀과의 팀당 경기 수는 $BB$로 다른 지역리그 팀들에 대해서 모두 동일하다. 즉, 한 팀 $XX$는 다른 지역리그에 있는 모든 팀 $ZZ$($\mathrm{\ne }X\backslash ne\; X$)와 각각 $BB$번의 경기를 한다. 단, $AA$와 $BB$는 $A=k\times BA\; =\; k\; \backslash times\; B$ ($kk$는 $11$ 이상의 정수)를 만족해야 한다.

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

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

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

입력

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

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

각 테스트 케이스는 하나의 줄에 네 개의 정수 $NN$, $MM$, $kk$, $DD$가 공백 하나를 사이로 두고 주어진다.

출력

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

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

3
2 3 3 60
2 2 1 18
2 2 1 4

54
18
-1