题目描述

请注意：本题与零食危机（简单版本）的区别仅在于测试数据数量与数据范围不同。

剑舞获得了奖学金（bushi），决定买些零食犒劳一下自己。他从城市 $a$ 出发，计划回到城市 $b$。不过，他必须避免经过某些特定的城市，这些城市的编号是某个整数 $c$ 的倍数，因为这些城市中会有川哥截胡，导致他的零食被抢走。

剑舞每次可以从城市 $x$ 移动到 $x+1$ 或 $x+2$ 的城市。他需要找到一条从城市 $a$ 到城市 $b$ 的最短路径，同时确保不会经过任何那些危险的城市。能帮他解决这个问题吗？

输入格式

第一行输入一个整数 $t\ (1≤t≤100)$，表示测试数据的数量。

接下来的 $t$ 行中，每行包含三个整数 $a , b , c\ (1≤a<b≤10^9,2≤c≤10^9)$ 表示一组测试数据。

数据保证 $a,b$ 不为 $c$ 的倍数

输出格式

输出 $t$行，每行一个整数表示答案。

1
2 7 3

3

解释 #1

对于样例，一种赶路方案为 $2→4→5→7$，总共需要 $3$ 天。