단체 대회

바샤는 친구들과 함께 새로운 단체 대회에 참가하려고 한다. 그가 익숙하게 여겨온 대회들과 달리, 이 대회에서는 한 팀에 임의의 수의 참가자가 들어갈 수 있다. 우승하려면 팀이 제시된 모든 문제를 풀어야 한다.

대회에는 두 종류의 문제가 있다. n개의 인터랙티브 문제와 m개의 일반 문제다. 바샤의 친구들은 각자 한 종류의 문제만 풀 수 있다. 친구가 인터랙티브 문제를 풀 수 있다면 문제 하나에 p분이 걸리고, 일반 문제를 풀 수 있다면 q분이 걸린다. 바샤는 두 종류 모두 풀 수 있으며, 친구들과 마찬가지로 인터랙티브 문제에 p분, 일반 문제에 q분을 쓴다.

팀 참가자들은 문제를 풀기 위해 임의의 수의 컴퓨터를 사용할 수 있다. 대회가 진행되는 동안 각 문제는 정확히 한 참가자가 풀며, 참가자들끼리 서로 대화하지 않는다.

길이가 t분인 대회에서 우승할 수 있는 팀을, 참가자 수가 최소가 되도록 바샤가 구성하도록 돕자.

예를 들어 100분 동안 진행되는 대회에 인터랙티브 문제 10개와 일반 문제 10개가 있고 p = q = 30이라면, 7명으로 팀을 구성할 수 있다. 바샤, 인터랙티브 문제를 푸는 친구 세 명, 일반 문제를 푸는 친구 세 명이다. 친구들은 각자 자기 종류의 문제를 세 개씩 풀고, 바샤는 인터랙티브 문제 하나와 일반 문제 하나를 푼다.

첫 번째 줄에 테스트 세트의 수 T가 주어진다(1 ≤ T ≤ 1000). 다음 T개 줄에 테스트 세트가 주어진다. 각 줄에는 다섯 개의 양의 정수 n, m, p, q, t가 주어지며, 각 수는 10000을 넘지 않는다. 또한 p ≤ t이고 q ≤ t이다.

각 테스트 세트마다 우승에 필요한 최소 팀 참가자 수를 한 줄에 하나씩 출력한다.