Lineup Counting Queries

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$."

• 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

Output the answer to each query on a separate line.

Lineups at various times:

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$.