Migrated from Lutece 1487 卿学姐把妹

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

卿学姐要去把妹了！！

卿学姐要把$N$个妹子

每个妹子被勾搭成功的概率是$P$

卿学姐想先定个小目标$K$

使得恰好有$K$个妹子被勾搭的概率最大！！

卿学姐想知道$K$是多少？

如果有多个$K$，输出最大的那个

Input

第一行一个整数$T$，表示有多少个测试点

第二行三个整数$N,A,B$，$N$表示妹子的数量，把妹成功的概率是$P=A/B$

$1\le N \le 10^{16}$

$1\le A \le 10^9$

$A\le B \le 10^9$

$1\le T \le 1000$

Output

一个整数$K$

Samples

2
2 1 2
3 1 1

1
3

Resources

每周一题 div2