你有两座由方块组成的塔,彼此相邻。最初,第一座塔的高度为 $$$a$$$,第二座塔的高度为 $$$b$$$。
通过一项操作,您可以:
- 拿一个方块并将其放置在其中一座塔上,使其高度增加$$$1$$$;
- 或拿两个方块并在每个塔上放置一个,将两个高度增加 $$$1$$$。然而,这只有在它们的高度相等的情况下才能完成。
您的目标是使第一座塔的高度等于 $$$c$$$,第二座塔的高度等于 $$$d$$$。您需要执行的最少操作次数是多少?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例由一行组成,其中包含 $$$4$$$ 整数 $$$a, b, c, d$$$ ($$$1 \le a \le c \le 10^8$$$; $$$1 \le b \le d \le 10^8$$$)。
输出
对于每个测试用例,输出一个整数 - 您必须执行的最小操作数。
示例
输入复制
51 2 3 51 1 1 12 6 3 83 3 6 42 4 7 7
输出复制
40335
注意
在第一个示例中,您可以首先在第一个塔上放置一个方块,使两个塔的高度等于 $$$2$$$。然后,您可以在每个塔上放置一个方块,将它们的高度提高到 $$$3$$$。之后,您可以在第二座塔上放置两个方块,将其高度增加到$$$5$$$。因此,在 $$$4$$$ 移动中,您可以使第一个塔的高度等于 $$$3$$$,第二个塔的高度等于 $$$5$$$。