MANIT is organising a practice Marathon Let's Run in Sportomania. This is a non-competitive Marathon.
MANIT just provides the circular track of circumference 10⁹+7 to the students and they can self evaluate them on the track. Track is bidirectional i.e. athelete can run in any direction.

Anurag, a enthusiastic athelete wants to evaluate himself and develope a strategy for his own evaluation.

Anurag starts his practice run at point S. He starts running at speed v . After each interval of time dt , he immediately increases his speed to n times and changes his direction. After some time T , he becomes tired and hence stop running.

Now Anurag calls his friend Ayush who was waiting for him at starting point to meet him at the same place where he stops. Anurag told his location to the Ayush. Find the minimum distance Ayush needs to travel?

Input:

The first line contains an integer, Q, denoting the number of queries.
The first and the only line of each query contain four space-separated integers: v, dt, n and T respectively as described in the statement.

Output:

For each query, find the minimum distance Ayush needs to travel in a single line.

Constraints:

1 ≤ Q ≤ 10⁵
1 ≤ v,dt,n,T ≤ 10⁹