Vova is playing a computer game. There are in total nn turns in the game and Vova really wants to play all of them. The initial charge of his laptop battery (i.e. the charge before the start of the game) is kk.

During each turn Vova can choose what to do:

• If the current charge of his laptop battery is strictly greater than aa, Vova can just play, and then the charge of his laptop battery will decrease by aa;
• if the current charge of his laptop battery is strictly greater than bb (b<ab<a), Vova can play and charge his laptop, and then the charge of his laptop battery will decrease by bb;
• if the current charge of his laptop battery is less than or equal to aa and bb at the same time then Vova cannot do anything and loses the game.

Regardless of Vova's turns the charge of the laptop battery is always decreases.

Vova wants to complete the game (Vova can complete the game if after each of nn turns the charge of the laptop battery is strictly greater than 00). Vova has to play exactly nn turns. Among all possible ways to complete the game, Vova wants to choose the one where the number of turns when he just plays (first type turn) is the maximum possible. It is possible that Vova cannot complete the game at all.

Your task is to find out the maximum possible number of turns Vova can just play(make the first type turn) or report that Vova cannot complete the game.

You have to answer qq independent queries.

Input

The first line of the input contains one integer qq (1≤q≤1051≤q≤105) — the number of queries. Each query is presented by a single line.

The only line of the query contains four integers k,n,ak,n,a and bb (1≤k,n≤109,1≤b<a≤1091≤k,n≤109,1≤b<a≤109) — the initial charge of Vova's laptop battery, the number of turns in the game and values aa and bb, correspondingly.

Output

For each query print one integer: -1 if Vova cannot complete the game or the maximumnumber of turns Vova can just play (make the first type turn) otherwise.

#include
using namespace std;
typedef long long ll;
ll q,k,n,a,b;
int main()
{
cin>>q;
while(q--)
{
cin>>k>>n>>a>>b;
ll x;
if((k-b*n)<=) cout<<-<<endl;
else
{

        x=(k-n\*b)/(a-b);if((k-n\*b)%(a-b)==)x--;  
        cout<<min(x,n)<<endl;  
    }

}  
return ;  

}

思路分析：提供了电池剩余电量k,要使用轮数n,玩游戏消耗电量a,边充电边玩消耗电量b。先输入查询轮数q。然后输入每轮的k、n、a、b。如果电量减去所有轮数使用b方法消耗电量剩余电量还是小于等于0，就输出-1，代表没有使用a方法，且不能完成n轮任务。否则n轮全用b方法会有剩余电量，设变量x为总电量减去假设n轮全使用b方法消耗后剩余的电量再除以a、b两种电量使用方式之差，如果总电量减去假设n轮全使用b方法消耗后剩余的电量再除以a、b两种电量使用方式的余数为0.x减1.再输出x和n的最小值就是a方式再能完成n轮任务且有电量剩余情况下能使用的最多轮数。

#include
using namespace std;
int main() {
long long q,cnt=-;
bool flag=false;
cin>>q;
long long k[q],n[q],a[q],b[q];
for(long long i=; i>k[i]>>n[i]>>a[i]>>b[i];
}
for(int i=; i) {
cnt=k[i]/a[i];
} else {
if(b[i]>=k[i]||b[i]*n[i]>=k[i]) {
cout<<-<=) {
if(cnt>n[i]) {// 9 17 18 15
cout<=k[i]) {
cout<<-<<endl;
}
}
}
cnt=-;
}
}

思路分析：先判断剩余电量k除以a方式消耗电量的值为正，再看最多可以使用几次a方式再加上剩余轮数全使用b方式的值要是小于剩余电量就输出使用a的次数cnt,否则将次数减一再进行同样判断。如果b方式消耗值大于剩余电量或者全部轮数使用b方式用电大于剩余电量k就将a的次数输出为-1，若全部轮数使用b方式用电小于等于剩余电量k就将a的次数输出为0。