Abhinav is far away from his home on Halloween night! He's incredible scared of being attacked by ghosts, so he wants to run home as quick as he can to maximize his chance of making it through the night safely.
We can model Abhinav's position and his home's position as points on a number line as $a$ and $h$, respectively. In a single second, Abhinav can move anywhere between $1$ and $d$ units. Given $a$, $h$, and $d$, can you figure out how fast Abhinav can make it back home?
The first line will consist of a single integer $T$ ($1 <= T <= 1000$) consisting of the number of test cases you will need to process. The next $T$ lines each consist of a single test case with $3$ space separated integers $a$, $h$, $d$ ($1 <= a, h, d <= 10^5$), which represent Abhinav's position, his home's position, and his max speed.
For each test case, output a single integer giving the minimum amount of time (in seconds) it will take Abhinav to reach his home.
## Input
The first line will consist of a single integer $T$ ($1 <= T <= 1000$) consisting of the number of test cases you will need to process. The next $T$ lines each consist of a single test case with $3$ space separated integers $a$, $h$, $d$ ($1 <= a, h, d <= 10^5$), which represent Abhinav's position, his home's position, and his max speed.
## Output
For each test case, output a single integer giving the minimum amount of time (in seconds) it will take Abhinav to reach his home.
[samples]
**Definitions**
Let $ S \in \Sigma^* $ be a string over $ \Sigma = \{ \text{a}, \text{b}, \dots, \text{z} \} $, initially of length $ n $.
Let $ q \in \mathbb{Z}^+ $ be the number of operations.
**Operations**
For each of the $ q $ operations:
1. **Delete**: Given $ l, r $, remove all characters at positions $ l $ to $ r $ inclusive.
2. **Insert**: Given character $ c \in \Sigma $ and position $ p $, insert $ c $ at position $ p $; shift all characters at positions $ \geq p $ one position right.
3. **Query**: Given $ l, r $, determine whether the substring $ S[l:r] $ is a palindrome.
**Constraints**
1. $ 1 \leq n, q \leq 3 \cdot 10^5 $
2. For each operation:
- Type 1: $ 1 \leq l \leq r \leq |S| $
- Type 2: $ 1 \leq p \leq |S| + 1 $, $ c \in \Sigma $
- Type 3: $ 1 \leq l \leq r \leq |S| $
3. $ S $ initially contains no combined "ae" character.
**Objective**
For each type-3 query, output "yes" if $ S[l:r] $ is a palindrome, otherwise "no".
All operations modify $ S $ in-place, and queries must be processed online.