문제

우솔이는 A 타입 칩 $A$개와 B 타입 칩 $B$개를 가지고 있다. ($0 \le A, B \le 10^9$) 우솔이는 다음과 같은 연산을 원하는 만큼 수행할 수 있다.

• B 타입 칩을 $c_B$개 이상 가지고 있다면, B 타입 칩 $c_B$개를 A 타입 칩 $c_A$개로 교환한다. ($1 \le c_A, c_B \le 10^9$)

우솔이는 추가로 종류가 무작위인 칩 $x$개를 받으려고 한다. 새로 받는 $x$개의 칩은 각각 A 타입 또는 B 타입 중 하나이다. $x$개의 칩이 어떤 조합으로 들어오더라도 우솔이가 항상 최종적으로 A 타입 칩을 $f_A$개 이상 가질 수 있음이 보장되는 최소의 비음수 정수 $x$를 구하시오. ($0 \le f_A \le 10^9$)

입력

첫째 줄에 독립적인 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 10^4$)

이어서 $T$개의 줄에 각 테스트 케이스를 나타내는 다섯 개의 정수 $A, B, c_A, c_B, f_A$가 공백으로 구분되어 주어진다. ($0 \le A, B, f_A \le 10^9$; $1 \le c_A, c_B \le 10^9$)

출력

각 테스트 케이스에 대한 정답을 별도의 줄에 출력한다.

주의: 이 문제에서 다루는 정수의 범위가 크므로, C/C++의 long long과 같은 64비트 정수 자료형을 사용해야 할 수도 있다.

예제 입력 1

2
2 3 1 1 6
2 3 1 1 4

예제 출력 1

1
0

예제 입력 2

5
0 0 2 3 5
0 1 2 3 5
1 0 2 3 5
10 10 2 3 5
0 0 1 1000000000 1000000000

예제 출력 2

9
8
7
0
1000000000000000000

점수

• 테스트 케이스 3: $c_A = c_B = 1$
• 테스트 케이스 4-5: 모든 경우에 대해 $x \le 10$
• 테스트 케이스 6-7: $c_A = 2, c_B = 3$
• 테스트 케이스 8-12: 추가 제약 조건 없음