有一排奶牛，初始时（即在时刻 $t = 0$）只包含位于位置 $0$ 的奶牛 $0$（这里，如果一只奶牛前面有 $k$ 只奶牛，则它处于位置 $k$）。在时刻 $t$（对于 $t=1,2,3,\dots$），位于位置 $0$ 的奶牛移动到位置 $\lfloor t/2\rfloor$，位于位置 $1\dots \lfloor t/2\rfloor$ 的每只奶牛都向前移动一个位置（即位置编号减 $1$），而奶牛 $t$ 加入队伍的末尾（位置 $t$）。

回答 $Q$（$1\le Q\le 10^5$）个独立的询问，每个询问的格式如下：

• 在编号为 $l_1\dots r_1$ 的奶牛中，有多少只在时刻 $t$ 之后立即位于位置 $l_2\dots r_2$？（$0\le l_1\le r_1\le t, 0\le l_2\le r_2 \le t, t\le 10^{18}$）

输入格式

第一行包含询问次数 $Q$。

接下来的 $Q$ 行，每行包含五个整数，表示一个格式为 "$l_1$ $r_1$ $l_2$ $r_2$ $t$" 的询问。

输出格式

对每个询问，在一行中输出答案。

样例

输入样例 1

4
0 9 0 9 9
3 5 4 5 9
4 5 3 5 9
1 1 3 3 9

输出样例 1

10
2
1
1

说明 1

不同时刻的队伍排列如下：

t = 0 | 0
t = 1 | 0 1
t = 2 | 1 0 2
t = 3 | 0 1 2 3
t = 4 | 1 2 0 3 4
t = 5 | 2 0 1 3 4 5
t = 6 | 0 1 3 2 4 5 6
t = 7 | 1 3 2 0 4 5 6 7
t = 8 | 3 2 0 4 1 5 6 7 8
t = 9 | 2 0 4 1 3 5 6 7 8 9

在 $t=9$ 时，从前到后的奶牛依次为 $[2,0,4,1,3,5,6,7,8,9]$。

对于第三个询问，位于位置 $3\dots 5$ 的奶牛为 $[1,3,5]$，其中只有一只奶牛的编号在 $4\dots 5$ 范围内（即奶牛 $5$）。

输入样例 2

1
0 1000000000000000000 0 1000000000000000000 1000000000000000000

输出样例 2

1000000000000000001

子任务

• 测试点 3：$Q\le 1000, t\le 100$
• 测试点 4-7：对于所有询问，满足 $l_1 = r_1$
• 测试点 8-14：对于所有询问，满足 $r_1 \leq 2 \cdot l_1$
• 测试点 15-21：无附加限制