Description

本题测试数据较弱，若想测试代码可去 原题

有3个跳跳棋，坐标分别为 a，b，c。

每个棋子都可以以 最右侧 的棋子为中点跳跃，若棋子 x 以棋子 y 为中点跳跃，到达的位置为 2y - x。

求最少通过多少次操作，能使得至少一个棋子坐标 \(\ge N\)。

Format

Input

第一行输入一个正整数 \(T(1 \le T \le 10^5)\)，表示数据组数

对于每组数据，输入一行四个正整数 \(a,b,c,N(1 < a < b < c < N \le 10^9)\)。

Output

每行输出一个正整数，表示最少的操作次数。

Sample 1

Input 1

3
1 2 3 10
2 3 4 20
3 4 5 30

Output 1

3
4
5

Input 2

3
1 2 3 10000
1 2 3 1000000
1 2 3 100000000

Output 2

17
27
36

Explain

对于样例 #1