题目描述
1941年，小日子过得还不错的岛国人在华北占领地区强迫中国人民到处建筑碉堡，封锁沟，几10万日本军不断地向华北抗日根据地进行扫荡，抗日战争进行最困难的时期，为了粉碎敌人的扫荡，坚持敌后游击战争，智慧的人民创造了地道战。由于特殊原因，需要将地道里两侧的物资进行快速转移，因过道空间非常狭窄，所以一次只能搬运一种物质，假设在搬运过程中出发地和目的地之间的过道全部被占用，且搬运一次需要时间r分钟，在这r分钟内不被占用的过道也可以同时搬运。一共有n处物资需要转移，为了尽快转移全部物资，大家需要多长时间。
输入
首行输入t （表示测试用例的数量）。每个测试用例都以包含整数 n 和时间r的开始，下列n行每行两个数据 a和b表示从a运输到b;（n不大于400）
输出
输出所需要时间（每行一个）
样例输入 Copy
3
4 10
10 20
30 40
50 60
70 80
2 10
1 3
2 200
3 10
10 100
20 80
30 50
样例输出 Copy
10
20
30