#306 실크의 노래 (강철 영혼)

Statement

Hollow Knight: Silksong의 팬인 은하는 DLC인 Sea of Sorrow의 출시를 기다리다가 지쳐서, 이 게임의 강철 영혼 모드에 도전해 보기로 했다.

이 게임의 주인공인 호넷은 적의 공격을 맞으면 체력이 $\color{red}{A}$ 만큼 감소하며, 회복 스킬을 사용하면 실크를 $1$ 소모해서 체력을 $\color{limegreen}{B}$ 만큼 회복할 수 있다. 그러나 최대 체력을 초과하여 회복하려고 할 경우 최대 체력까지만 회복된다.

은하는 적의 패턴을 파악하기 위해 회복 스킬을 적절히 사용하면서 최대한 오래 버텨 보기로 했다. 전투가 시작될 때 호넷의 체력은 최대 체력 $H$ 와 같으며, 가진 실크의 양은 $S$ 이다. 체력이 $0$ 이하가 되는 순간까지 호넷이 맞을 수 있는 공격의 최대 횟수를 구하라.

은하는 자신이 원할 때 언제든지 회복 스킬을 사용할 수 있으며, 전투 도중 실크를 추가로 얻는 경우는 없다.

Input

첫째 줄에 테스트 케이스의 수 $Q$ 가 주어진다. $(1 \leq Q \leq 100\,000)$

다음 $Q$ 개의 줄에 정수 $H$ , $S$ , $A$ , $B$ 가 공백을 사이에 두고 주어진다. $(1 \leq H, S, A, B \leq {10}^{18})$

Output

체력이 $0$ 이하가 되는 순간까지 호넷이 맞을 수 있는 공격의 최대 횟수를 $n$ 이라고 하자. 문제의 제한 조건에서 항상 $n \leq {10}^{36}$ 를 만족함을 증명할 수 있다. 각 테스트 케이스마다 $n \pmod{{10}^{18}}$ 의 값을 한 줄에 하나씩 출력한다.

Samples

입력

4
8 2 2 3
6 5 4 3
1 999999999999 2 3
1000000000000000000 1000000000000000000 1 1000000000000000000

출력

테스트 케이스 1의 설명

$8 \xrightarrow{\color{red}{-2}} 6 \xrightarrow{\color{red}{-2}} 4 \xrightarrow{\color{red}{-2}} 2 \xrightarrow{\color{limegreen}{+3}} 5 \xrightarrow{\color{limegreen}{+3}} 8 \xrightarrow{\color{red}{-2}} 6 \xrightarrow{\color{red}{-2}} 4 \xrightarrow{\color{red}{-2}} 2 \xrightarrow{\color{red}{-2}} \color{red}{0}$

최대 $7$ 번의 공격을 맞을 수 있다. 연속으로 $2$ 번 회복하는 것도 가능하다.

테스트 케이스 2의 설명

$6 \xrightarrow{\color{red}{-4}} 2 \xrightarrow{\color{limegreen}{+3}} 5 \xrightarrow{\color{red}{-4}} 1 \xrightarrow{\color{limegreen}{+3}} 4 \xrightarrow{\color{limegreen}{+2}} 6 \xrightarrow{\color{red}{-4}} 2 \xrightarrow{\color{limegreen}{+3}} 5 \xrightarrow{\color{red}{-4}} 1 \xrightarrow{\color{limegreen}{+3}} 4 \xrightarrow{\color{red}{-4}} \color{red}{0}$

회복을 언제 하더라도 $5$ 번의 공격을 맞으면 체력이 $0$ 이하가 된다. 체력 $4$ 에서 회복을 했을 때 최대 체력 $6$ 을 넘을 수 없음에 유의하라.

테스트 케이스 3의 설명

몇 번 회복하든 상관 없이 $1$ 번 맞으면 죽는다.

테스트 케이스 4의 설명

$n = {10}^{36}$ 이므로, ${10}^{36} \pmod{{10}^{18}} = 0$ 을 출력한다.

Notes

계산 과정 중 값이 커질 수 있으므로 일부 프로그래밍 언어에서는 $128$ 비트 정수 변수(C++: __int128)를 사용해야 할 수도 있음에 유의하라.

해설

해설 보기