17374번 - 비트베리

비트베리는 국내 최다 사용자를 확보하고 있는 간편암호화폐 지갑이다. 비트베리의 가장 큰 특징 중 하나는 카카오 계정으로 지갑을 만들고, 전화번호로 암호화폐를 주고받을 수 있는 점이다.

페카즈는 비트베리의 특징을 이용해 자신이 보유한 다양한 종류의 암호화폐를 친구 빈센트와 상호 교환하고자 한다. 현재 페카즈의 비트베리 지갑 속에는 P개의 비트와 Q개의 베리가 들어 있다. 페카즈의 친구 빈센트는 엄청난 부자여서, 자신의 비트베리 지갑 속에 비트, 베리, 그리고 또 다른 단위인 코인과 비트코인을 각각 10¹⁰⁰개씩 가지고 있다.

페카즈는 빈센트와 아래의 거래를 원하는 순서대로 원하는 만큼 반복할 수 있다.

• 빈센트에게 비트 A개를 주고 코인을 B개 받는다.
• 빈센트에게 코인 B개를 주고 비트를 A개 받는다.
• 빈센트에게 베리 C개를 주고 코인을 D개 받는다.
• 빈센트에게 코인 D개를 주고 베리를 C개 받는다.
• 빈센트에게 비트 1개와 코인 1개를 주고 비트코인을 1개 받는다.

물론 거래를 하기 위해 빈센트에게 줘야 하는 암호화폐가 부족하다면 거래를 진행할 수 없다.

페카즈는 최선의 거래를 하여 자신이 갖고 있는 비트코인의 개수를 최대화하고자 한다. 페카즈가 만들 수 있는 비트코인의 최대 개수를 출력하는 프로그램을 작성하라.

첫 번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 1,000)가 주어진다.

다음 T개의 줄에는 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄에는 하나의 테스트 케이스를 구성하는 여섯 개의 정수 P, Q, A, B, C, D (0 ≤ P, Q ≤ 10,000, 1 ≤ A, B, C, D ≤ 10,000)가 공백 하나씩을 사이에 두고 주어진다.

각각의 테스트 케이스마다, 페카즈가 만들 수 있는 비트코인의 최대 개수를 한 개의 줄에 출력한다.