뒤에 남은 자들

시간 제한1초메모리 제한2048 MB

요약

정식 러너 n명, 일반 러너 k명, 기준 비율 a/b가 주어졌을 때 모든 일반 러너를 정식 러너로 바꾸는 최소 훈련 횟수를 구합니다. 불가능하면 -1을 출력합니다.

난이도: 보통10점 중 5점
유형: 수학, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

달리기 동호회에는 정규 러너와 초보 러너가 있다. 동호회는 정규 러너와 초보 러너가 섞인 훈련 달리기를 여러 번 계획한다. 정규 러너는 초보 러너보다 빠른 페이스로 달려서 초보 러너를 뒤에 남겨 둔다.

모든 회원을 정규 러너로 만들려면 훈련 달리기에 참여할 정규 러너와 초보 러너 수를 신중하게 골라야 한다. 훈련 달리기에 정규 러너 $x$ 명과 초보 러너 $y$ 명이 있을 때 $\frac{x}{x+y}$ 가 기준 $\frac{a}{b}$ 이상이면, 달리기가 끝난 뒤 초보 러너 $y$ 명 모두가 정규 러너를 따라잡으려는 압박을 받아 그때부터 정규 러너가 된다.

동호회의 모든 회원을 정규 러너로 바꾸는 데 필요한 훈련 달리기의 최소 횟수를 구하라.

입력

첫 줄에 테스트 케이스의 수 $t$ ( $1\leq t \leq 100$ )가 주어진다. 이어지는 $t$ 개의 줄에는 정수 $n$ , $k$ , $a$ , $b$ ( $1 \leq n, k, a, b \leq 10^{9}$ 이고 $a \leq b$ )가 한 줄에 하나씩 주어진다. $n$ 은 정규 러너의 수, $k$ 는 초보 러너의 수, $\frac{a}{b}$ 는 초보 러너를 정규 러너로 바꾸는 기준이다.

출력

각 테스트 케이스마다 초보 러너를 모두 정규 러너로 바꾸는 데 필요한 최소 훈련 달리기 횟수를 한 줄에 출력한다. 불가능하면 $-1$ 을 출력한다.

예제1

예제 1
입력
```
3
9 5 5 6
2 7 1 8
3 4 1 5
```
예상 출력
```
3
1
1
```