NDT - New Data Type

Little boy maze invented a brand new data type that can store data from 1 to M inclusive. The speciality of the invented data type is if you want to store a data out of the range it can round the data and map with invented data type.

for example if the range is 1 to 7 and you want to store 9 then the system round 9 and map with 2.

Now you're given a number in the format  AB and the upper limit M of range. Can you round the number to map with new data type?

Input

Input starts with T <= 100000.

in the next T lines there will be three integers(1 <= A, B <= 1000000000000000000, 1 < M < 1000000000).

Output

For each case print the desire output.

Example

Input:
2
2 3 5
4 2 15

Output:
3
1

Added by:Jisan
Date:2019-04-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2023-08-21 21:23:13 Rafail Loizou
Pay attention: "a brand new data type that can store data from 1 to M inclusive". From 1 to M not from 0 to M-1. Costed me 3 WAs.
2019-05-01 03:56:46
Please avoid setting TL below 0.5s. The current 0.07s is less than some slower language interpreters need to launch, and those that do won't even manage to process the input of 300000 integers in that time.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.