디펜스

당신은 성의 주인이 되어 몰려오는 몬스터들을 물리쳐야 한다.

성은 길이 $N$의 일차원 경로의 좌표 $N$에 위치해 있다. 총 $M$초 동안 매초 한 마리의 몬스터가 좌표 $1$에서 소환된다. 이미 소환되어 있던 몬스터는 매초 좌표가 $1$만큼 증가하는 방향으로 전진한다.

몬스터가 성에 도달하면 성은 공격을 받고, 그 몬스터는 소멸한다. 모든 몬스터의 체력은 $H$이고, 당신의 공격력은 $K$이다.

당신은 매초 살아 있는 몬스터 한 마리를 골라 $K$의 데미지를 줄 수 있다. 공격을 받은 몬스터의 체력은 $K$만큼 감소하고, 체력이 $0$ 이하가 되면 해당 몬스터는 소멸한다.

몬스터가 소환되자마자 공격하는 것은 가능하다. 또한 몬스터가 좌표 $N$으로 이동하는 순간 그 몬스터를 공격해 소멸시키면, 그 몬스터는 성을 공격하지 못한 것으로 판정한다.

더 이상 살아 있는 몬스터가 없을 때까지 공격할 수 있다. 즉, 마지막 몬스터가 소환된 이후에도 아직 살아 있는 몬스터가 있다면 계속 공격할 수 있다.

성을 최소한으로 공격받게 하기 위해 최대한 많은 몬스터를 잡고자 한다. 잡을 수 있는 몬스터 수의 최댓값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $N_1\ M_1\ H_1\ K_1$ $N_2\ M_2\ H_2\ K_2$ $\vdots$ $N_T\ M_T\ H_T\ K_T$

각 테스트 케이스마다 잡을 수 있는 몬스터 수의 최댓값을 한 줄에 하나씩 출력한다.

• $1 \le T \le 100\,000$.
• $1 \le N,M,H,K \le 1\,000\,000\,000$.
• 입력으로 주어지는 모든 수는 정수이다.