Background

Special for beginners, ^_^

Description

王老师做了个梦，梦见他能够在x轴上腾云驾雾。

如果他位于左半轴上，就被如来佛抓住了，动不了了。

否则，如果他当前位置是x，那么他下一时刻的位置就是ax - b。

给出王老师的初始位置位于x、请问他能到达的最左位置是哪里？

Format

Input

第一行一个整数 $T$（<=1e6），表示数据组数。

对于每组数据，输入一行三个整数 $x,a,b$(都是不超过1e9的自然数)。

Output

对于每组数据，输出一行一个整数表示答案。

Samples

2
6 2 4
5 3 16

6
-1

Limitation

1s, 1024KiB for each test case.