문제 133
조건을 만족하는 가장 작은 분수
정수 $N$, $A$, $B$, $S$가 주어진다. 다음 조건을 만족하는 기약분수 $p/q$ 중 가장 작은 것을 구해 보자. 분자 $p$는 음이 아닌 정수이고, 분모 $q$는 양의 정수이다.
\[ 0\le p\le q\le N,\qquad \gcd(p,q)=1. \]
$S=0$이면 $p/q\ge A/B$를, $S=1$이면 $p/q>A/B$를 추가로 만족해야 한다.
입력
첫 번째 줄에 테스트 케이스의 수를 의미하는 정수 $T$가 주어진다. $(1\le T\le20\,000)$
두 번째 줄부터 $T$개의 줄에 걸쳐 정수 $N$, $A$, $B$, $S$가 공백으로 구분되어 주어진다. $(1\le N,B\le10^9; 0\le A\le B; S\in\{0,1\}; S=1\Rightarrow A<B)$
출력
각 테스트 케이스에 대해 답의 분자 $p$와 분모 $q$를 공백으로 구분하여 한 줄에 출력한다.
예제 입력 1
6 1 0 1 0 1 0 1 1 5 1 3 0 5 1 3 1 5 1 1 0 1000000000 0 1 1
예제 출력 1
0 1 1 1 1 3 2 5 1 1 1 1000000000