### 问题描述
**请注意：本题与情报传递 $2$ 的区别仅在于测试数据数量与数据范围不同。**
在北宋末年的乱世，梁山泊的好汉们经常要穿梭于各地，传递情报和策划行动。一天，智多星吴用接到了一项紧急任务，需要派遣鲁智深从一个编号为 $a$ 的城市出发，前往编号为 $b$ 的城市，以商讨与盟友的下一步行动。
然而，朝廷已经在沿途布下了天罗地网，凡是编号为 $c$ 的倍数的城市都设有重重哨卡，一旦经过这些城市，梁山的行踪就会被朝廷发现，后果不堪设想。因此，鲁智深在赶往 $b$ 号城市的路上，必须避开这些编号为 $c$ 倍数的城市。
每次，鲁智深可以选择沿着大道前进，假设当前鲁智深在 $x$ 号城市，那么经过一天徒步他可以到达 $x+1$ 或 $x+2$ 号城市 ，但无论如何都不能进入那些危险的城市。为了万无一失，吴用需要设计出一条最安全且最短的路径，让鲁智深能以最少的步数到达 $b$ 号城市。
现在，请你帮助吴用计算：鲁智深最少需要多少天，才能从 $a$ 号城市安全抵达 $b$ 号城市？
### 输入格式
第一行输入一个整数 $t(t=1)$ 表示测试数据的数量。
接下来 $t$ 行，每行包括三个整数 $a,b,c(1 \leq a