B. Billy Loves Zeros
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Once upon a time, Billy had an array $$$a$$$ of length $$$n$$$ such that $$$a_i = i$$$ for all $$$1\leq i \leq n$$$, and an integer $$$m$$$ ($$$m \gt n$$$). The array $$$a$$$ was then cyclically shifted to the right by $$$k$$$ positions to form the array $$$b$$$.

For example, when $$$n= 5$$$ and $$$k = 2$$$, the arrays $$$a$$$ and $$$b$$$ are given as follows: $$$$$$ a = [1,2,3,4,5] \longrightarrow \text{cyclic right-shift by 2} \longrightarrow b=[4,5,1,2,3] $$$$$$

Billy may perform one type of operation on array $$$b$$$, consisting of two steps:

  1. Choose two integers $$$l$$$ and $$$r$$$ such that $$$1\leq l \leq r \leq n$$$
  2. For each index $$$i \in [l, r]$$$, set $$$b_i \leftarrow (b_i + 1) \text{ mod } m$$$

Billy especially loves arrays in which every element is $$$0$$$. Help Billy find the minimum number of operations required to transform $$$b$$$ into $$$[0, 0,\cdots, 0]$$$.

Input

The first line contains an integer $$$t$$$ ($$$1\leq t \leq 2\times 10^5$$$), the number of test cases.

Each test case consists of a single line containing three integers $$$n, k, m$$$ ($$$1\leq n \lt m \leq 10^9$$$, $$$0 \leq k \leq n-1$$$), denoting the size of the array $$$b$$$, the right-shift offset $$$k$$$ and the modulus $$$m$$$.

Output

$$$t$$$ lines, the answer to each test case on a single line.

Example
Input
2
1 0 3
5 2 6
Output
2
6
Note

There are $$$2$$$ test cases.

In the first test case, $$$a = [1]$$$ and since $$$k = 0$$$, $$$b = a = [1]$$$. Let $$$f(l,r)$$$ denote one application of the operation to the subarray from index $$$l$$$ to index $$$r$$$:

  • Operation 1 – $$$f(1,1) = [(1 + 1) \text{ mod } 3] = [2]$$$
  • Operation 2 – $$$f(1,1) = [(2 + 1) \text{ mod } 3] = [0]$$$

After these two operations, $$$b = [0]$$$. Therefore the minimum number of operations is $$$2$$$.