题目描述

剑舞获得了奖学金（bushi），决定买些零食犒劳一下自己。他从城市 (a) 出发，计划回到城市 (b)。不过，他必须避免经过某些特定的城市，这些城市的编号是某个整数 (c) 的倍数，因为这些城市中会有川哥截胡，导致他的零食被抢走。 剑舞每次可以从城市 (x) 移动到 (x+1) 或 (x+2) 的城市。他需要找到一条从城市 (a) 到城市 (b) 的最短路径，同时确保不会经过任何那些危险的城市。能帮他解决这个问题吗？

输入格式

第一行输入一个整数 t ( 1≤t≤100 )，表示测试数据的数量。 接下来的 t 行中，每行包含三个整数 a , b , c (1≤a 数据保证a,b不为c的倍数

输出格式

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

1
2 7 3

3

提示

对于样例，一种赶路方案为2→4→5→7，总共需要 3 天。 请注意：本题与零食危机(hard version)的区别仅在于测试数据数量与数据范围不同。