Timer

As punishment for acting up at school, Petya is serving a sentence under house arrest. In his room there is a timer that shows how long Petya has already been serving his punishment. Every second the number on the timer increases by one. Wanting to shorten his punishment, Petya found a vulnerability in the timer. If the timer currently shows $a$ seconds, then, using the vulnerability, Petya can make it show $b$ seconds, where $b$ is the smallest number greater than or equal to $a$ that is divisible by a given number $y$.

Petya wants the timer to show as many seconds as possible. However, Petya also does not want to get caught, so he will not use the vulnerability more than $k$ times. What is the maximum number on the timer that Petya can get after $t$ real seconds? At the moment Petya discovered the vulnerability, the timer showed the number $x$.

For example, suppose that at the moment the vulnerability was discovered the timer showed $x = 9$, $y = 10$, Petya plans to use the vulnerability at most $k = 10$ times, and $t = 2$. Then the maximum number Petya can get on the timer is 30, and to do this he must act as follows. Immediately using the vulnerability, he gets the value 10 on the timer. After 1 second the timer will show 11, and by using the vulnerability Petya gets 20 on it. After another second it will be 21, and by using the vulnerability Petya will get the value 30.

The first line contains the integer $T$ ($1 \le T \le 10^4$), the number of test cases. Each of the following $T$ lines contains four integers: $x$, $y$, $k$, and $t$. (All numbers are between 1 and $10^9$ inclusive.)

For each of the $T$ test cases, output a single number: the maximum possible number the timer can show after $t$ seconds.