22109번 - Таймер 다국어

문제

За хулиганство в школе Петя отбывает наказание под домашним арестом. В его комнате есть таймер, который показывает, сколько Петя уже пробыл под наказанием. Каждую секунду число на таймере увеличивается на единицу. Петя, желая сократить время своего наказания, нашел в нем уязвимость. Пусть таймер в настоящий момент показывает a секунд, тогда, использовав найденную уязвимость, Петя может сделать так, чтобы он показывал b секунд, где b — наименьшее число, большее либо равное a, которое делится на заданное число y.

Петя хочет, чтобы таймер показывал как можно больше секунд. Однако, Петя также не хочет попасться, поэтому он не будет использовать найденную уязвимость больше, чем k раз. Какое максимальное число на таймере Петя может получить через t реальных секунд? В момент, когда Петя обнаружил уязвимость, на таймере было число x.

Например, пусть в момент обнаружения уязвимости на таймере было число x = 9, y = 10, Петя планирует применить уязвимость не более k = 10 раз и t = 2. Тогда максимальное число, которое Петя может получить на таймере равно 30, для этого ему необходимо действовать так. Сразу применив уязвимость, он получает на таймере значение 10. Через 1 секунду на таймере будет значение 11, применив уязвимость, Петя получает на нем значение 20. Еще через секунду на таймере будет 21, применив уязвимость, Петя получит значение 30.

입력

Первая строка содержит целое число T (1 ≤ T ≤ 10⁴) — количество тестовых примеров. В каждой из следующих T строк содержится по четыре целых числа: x, y, k и t. (все числа находятся в диапазоне от 1 до 10⁹).

출력

Для каждого из T тестовых примеров выведите единственное число — максимальное возможное число, которое может показывать таймер через t секунд,

제한

힌트