GG NO RE OMG CHEATZ

문제

이 문제를 풀기 위해 보드게임 Risk를 알아야 하는 것은 아니다. 이 문제에 나오는 주사위는 모두 여섯 면짜리 주사위다.

Rizk는 불가리아식 Risk다. 각자 군대를 이끄는 두 사람이 겨루며, 자기 차례에는 공격을 하거나 군대에 유닛을 더할 수 있지만 두 가지를 한꺼번에 할 수는 없다. 공격은 다음과 같이 진행한다.

공격하는 A의 유닛은 $U_a$ 개, 방어하는 B의 유닛은 $U_b$ 개다. 공격자는 주사위를 $D_a$ 개까지, 방어자는 $D_d$ 개까지 쓸 수 있다. 한 번의 공격은 다음 단계를 반복한다.

A가 주사위를 $\min(D_a, U_a)$ 개 굴린다.
B가 주사위를 $\min(D_d, U_b)$ 개 굴린다. 원래 Risk와 다른 부분이다.
두 사람은 각자 굴린 주사위를 큰 값부터 작은 값 순으로 정렬하고 앞에서부터 하나씩 짝지어 비교한다. 예를 들어 A가 2, 5, 1, 3을 굴리고 B가 4, 1, 3을 굴렸다면 5와 4를 비교하고, 다음으로 3과 3을, 마지막으로 2와 1을 비교한다. 주사위를 더 많이 굴린 쪽에서 남는 작은 주사위는 어떤 비교에도 쓰이지 않는다.
비교마다 진 쪽이 유닛을 하나 잃는다. 값이 같으면 방어자가 이긴다. 위 예에서 A는 유닛 1개를, B는 2개를 잃는다.
두 사람 모두 유닛이 1개 이상 남아 있으면 1번으로 돌아간다.

전투가 끝났을 때 유닛이 남아 있는 쪽이 이긴다. 유닛이 남는 사람은 항상 정확히 한 명이다.

마이크와 동생은 몇 시간째 게임 중이다. 둘 다 지는 것이 두려워 아무도 공격하지 않는다. 이제 마이크의 차례인데, 마이크는 이기려고 조금 속이기로 했다. 마이크는 이번 차례에 이길 확률이 75% 이상일 때만 공격한다. 마이크의 유닛은 $X$ 개, 동생의 유닛은 $Y$ 개다. 이번 차례에 이길 확률을 75% 이상으로 만들려면 마이크는 유닛을 최소 몇 개나 몰래 넣어야 하는가?

입력

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 다음 $T$ 개의 줄에는 각각 정수 $D_a$ , $D_d$ , $X$ , $Y$ 가 공백으로 구분되어 주어지며, 의미는 문제에서 설명한 것과 같다.

$1 \le T \le 30$
$1 \le D_a, D_d \le 4$
$1 \le X, Y \le 500$
마이크의 유닛을 하나 더하거나 빼도 승리 확률이 $0.75$ 에 $10^{-6}$ 보다 가까워지는 테스트 케이스는 없다.

출력

각 테스트 케이스마다 마이크가 이번 차례에 이길 확률을 75% 이상으로 만드는 데 필요한 추가 유닛의 최솟값을 한 줄에 하나씩 출력한다. 이미 확률이 75% 이상이면 0을 출력한다.