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,…, the cow at position 0 moves to position ⌊t/2⌋, every cow in positions 1 ⌊t/2⌋moves forward one position, and cow t joins the line at the end of the line (position t).
Answer Q (1≤Q≤105) independent queries each of the following form:
Out of cows l1…r1, how many are located at positions l2…r2 immediately after time t? (0≤l1≤r1≤t,0≤l2≤r2≤t,t≤1018)
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains Q, the number of queries.
The next Q lines each contain five integers specifying a query of the form "l1 r1 l2 r2 t."
OUTPUT FORMAT (print output to the terminal / stdout):
Output the answer to each query on a separate line.
SAMPLE INPUT:
4
0 9 0 9 9
3 5 4 5 9
4 5 3 5 9
1 1 3 3 9
SAMPLE OUTPUT:
10
2
1
1
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…5 are [1,3,5], and only one of them is in the range 4…5.
SAMPLE INPUT:
1
0 1000000000000000000 0 1000000000000000000 1000000000000000000
SAMPLE OUTPUT:
1000000000000000001
SCORING:
Input 3: Q≤1000,t≤100
Inputs 4-7: l1=r1
for all queries
Inputs 8-14: r1≤2⋅l1 for all queries
Inputs 15-21: No additional constraints
Problem credits: Agastya Goel and Benjamin Qi