Square Game

For an integer $k$ at least 2, an operation that replaces $k$ copies of $k$ with one $k^2$ is called a "square".

You are given $n$ integers $a_1, a_2, \ldots, a_n$. Write a program that processes the following query.

• $l$ $r$: Find the maximum number of squares that can be performed on the sequence $a_l, a_{l+1}, \ldots, a_r$, and print it.

For example, in the sequence $2, 4, 2, 4, 2, 2$, replacing two 2s with 4 twice gives $4, 4, 4, 4$. Then the four 4s can be replaced with 16. That makes 3 squares in total, so the maximum number of squares for this sequence is 3.

The first line contains $T$, the number of test cases. The $T$ test cases follow. ($1 \le T \le 32$)

The first line of each test case contains $n$. ($1 \le n \le 50\,000$)

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$, separated by spaces. ($1 \le a_i \le 1\,000\,000\,000$)

The next line contains $Q$, the number of queries. ($1 \le Q \le 50\,000$)

Each of the next $Q$ lines contains two integers $l_i$ and $r_i$, separated by a space, which describe the $i$-th query. ($1 \le l_i \le r_i \le n$)

For each test case, print "Case #$C$" on the first line, where $C$ is the test case number.

The next $Q$ lines each contain the maximum number of squares that can be performed for the corresponding query.