题目描述

有一条奶牛队列。初始时（即 \(t=0\)）队列中只有编号为 \(0\) 的奶牛，且它位于位置 \(0\)。如果一头奶牛前面有 \(k\) 头奶牛，那么称它位于位置 \(k\)。

对于每个时刻 \(t=1,2,3,\dots\)，队列按如下规则变化：

• 原来位于位置 \(0\) 的奶牛移动到位置 \(\left\lfloor \frac{t}{2} \right\rfloor\)
• 原来位于位置 \(1 \dots \left\lfloor \frac{t}{2} \right\rfloor\) 的奶牛全部向前移动一格
• 编号为 \(t\) 的奶牛加入队尾，也就是位置 \(t\)

现在有 \(Q\) 个独立询问，满足 \(1 \le Q \le 10^5\)。每个询问给定五个整数 \(l_1,r_1,l_2,r_2,t\)，你需要回答：

• 在时刻 \(t\) 之后，编号位于区间 \([l_1,r_1]\) 中的奶牛里，有多少头的当前位置落在区间 \([l_2,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

输出

10
2
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,5]\) 中，因此答案为 \(1\)。

样例 2

输入

1
0 1000000000000000000 0 1000000000000000000 1000000000000000000

输出

1000000000000000001

数据范围

• 输入 3：\(Q \le 1000, t \le 100\)
• 输入 4-7：所有询问都满足 \(l_1 = r_1\)
• 输入 8-14：所有询问都满足 \(r_1 \le 2l_1\)
• 输入 15-21：无额外限制

命题信息

原题命题：Agastya Goel、Benjamin Qi