문제

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}$)

입력

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 the answer to each query on a separate line.

예제 입력 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

예제 입력 2

1
0 1000000000000000000 0 1000000000000000000 1000000000000000000

예제 출력 2

1000000000000000001

점수

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