Problem Description

There is a line of cows, initially (i.e. at time $t = 0$) containing only cow $0$ at position $0$ (here, a cow is at position $k$ if there are $k$ cows in front of it). At time $t$ for $t=1,2,3,\dots$, the cow at position 0 moves to position $\lfloor t/2\rfloor$, every cow in positions $1\dots \lfloor t/2\rfloor$ moves forward one position, and cow $t$ joins the line at the end of the line (position $t$).

Answer $Q$ ($1\le Q\le 10^5$) independent queries each of the following form:

• Out of cows $l_1\dots r_1$, how many are located at positions $l_2\dots r_2$ immediately after time $t$? ($0\le l_1\le r_1\le t, 0\le l_2\le r_2 \le t, t\le 10^{18}$)

Input Format

The first line contains $Q$, the number of queries.

The next $Q$ lines each contain five integers specifying a query of the form "$l_1$ $r_1$ $l_2$ $r_2$ $t$".

Output Format

Output the answer to each query on a separate line.

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

1
0 1000000000000000000 0 1000000000000000000 1000000000000000000

1000000000000000001

Hint

Lineups at various times:

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

At $t=9$ the cows from front to back are $[2,0,4,1,3,5,6,7,8,9]$.

To answer the third query, the cows at positions $3\dots 5$ are $[1,3,5]$, and only one of them is in the range $4\dots 5$.

• Input 3: $Q\le 1000, t\le 100$
• Inputs 4-7: $l_1 = r_1$ for all queries
• Inputs 8-14: $r_1 \leq 2 \cdot l_1$ for all queries
• Inputs 15-21: No additional constraints.