/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
問題文
あなたはゲームをプレイしています。
このゲームでは、レベル x のキャラクタをレベル x+1 に上げるためには Ax+B 個の宝石を消費する必要があります。
宝石を N 個持っているとき、レベル 0 のキャラクタのレベルをいくつまで上げることができますか？
Q 個のテストケースに答えてください。
制約
- 1 \leq Q \leq 10^5
- 1 \leq A,B \leq 10^9
- 0 \leq N \leq 10^{18}
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
Q
\mathrm{testcase}_1
\mathrm{testcase}_2
\vdots
\mathrm{testcase}_Q
\mathrm{testcase}_i は i 番目のテストケースを表し、各テストケースは以下の形式で与えられる。
N A B
出力
答えを出力せよ。
入力例 1
3 10 2 3 1000000000000000000 1 1 0 1000000000 1000000000
出力例 1
2 1414213561 0
1 つ目のテストケースにおいて、レベルを上げるために必要な宝石の個数は以下の通りです。
- レベル 0 からレベル 1 に上げるために 3 個
- レベル 1 からレベル 2 に上げるために 5 個
- レベル 2 からレベル 3 に上げるために 7 個
宝石を 10 個持っているとき、レベル 0 のキャラクタをレベル 2 まで上げることができます。
Problem Statement
You are playing a video game.
In this game, raising a character from level x to level (x+1) requires consuming (Ax+B) gems.
If you have N gems, to what level can you raise a level-0 character?
Answer Q test cases.
Constraints
- 1 \leq Q \leq 10^5
- 1 \leq A,B \leq 10^9
- 0 \leq N \leq 10^{18}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
Q
\mathrm{testcase}_1
\mathrm{testcase}_2
\vdots
\mathrm{testcase}_Q
\mathrm{testcase}_i represents the i-th test case given in the following format:
N A B
Output
Print the answer.
Sample Input 1
3 10 2 3 1000000000000000000 1 1 0 1000000000 1000000000
Sample Output 1
2 1414213561 0
For the first test case, the number of gems required to raise the level is as follows:
- 3 gems to raise it from level 0 to level 1.
- 5 gems to raise it from level 1 to level 2.
- 7 gems to raise it from level 2 to level 3.
If you have 10 gems, you can raise a level-0 character up to level 2.