타이머

학교에서 장난을 친 벌로 페티야는 가택 연금형을 살고 있다. 그의 방에는 지금까지 벌을 받은 시간을 초 단위로 표시하는 타이머가 있다. 타이머의 숫자는 매초 1씩 증가한다. 형량을 줄이고 싶었던 페티야는 타이머에서 취약점을 찾아냈다. 타이머가 현재 $a$초를 표시하고 있을 때, 이 취약점을 이용하면 타이머가 $b$초를 표시하도록 만들 수 있다. 여기서 $b$는 $a$ 이상이면서 주어진 수 $y$로 나누어지는 가장 작은 수이다.

페티야는 타이머가 최대한 큰 수를 표시하기를 원한다. 하지만 들키고 싶지도 않기 때문에 취약점을 $k$번 넘게 사용하지 않는다. 페티야가 취약점을 발견한 순간 타이머에는 $x$가 표시되어 있었다면, 실제로 $t$초가 흐른 뒤 타이머에 표시될 수 있는 최댓값은 얼마인가?

예를 들어 취약점을 발견한 순간 타이머에 $x = 9$가 표시되어 있었고, $y = 10$, 취약점을 최대 $k = 10$번 사용할 계획이며 $t = 2$라고 하자. 그러면 페티야가 타이머에서 얻을 수 있는 최댓값은 30이며, 이를 위해 그는 다음과 같이 행동해야 한다. 곧바로 취약점을 사용하면 타이머는 10이 된다. 1초가 지나면 타이머는 11이 되고, 취약점을 사용하면 페티야는 20을 얻는다. 다시 1초가 지나면 21이 되고, 취약점을 사용하면 30을 얻는다.

첫 번째 줄에는 정수 $T$ ($1 \le T \le 10^4$)가 주어진다. 이는 테스트 예시의 수이다. 다음 $T$개의 줄에는 각각 네 개의 정수 $x$, $y$, $k$, $t$가 주어진다. (모든 수는 1 이상 $10^9$ 이하이다.)

각 테스트 예시마다 $t$초 뒤에 타이머가 표시할 수 있는 최댓값을 한 줄에 하나씩 출력한다.