스퀘어 게임

2 이상의 정수 $k$에 대해, $k$개의 $k$를 $k^2$ 한 개로 바꾸는 작업을 "스퀘어"라고 하자.

정수 $n$개 $a_1, a_2, \ldots, a_n$이 주어진다. 다음 쿼리를 처리하는 프로그램을 작성하시오.

• $l$ $r$: 수열 $a_l, a_{l+1}, \ldots, a_r$에서 가능한 스퀘어의 최대 횟수를 구하여 출력한다.

예를 들어, 수열 $2, 4, 2, 4, 2, 2$에서 2개의 2를 4로 바꾸는 작업을 두 번 하면 $4, 4, 4, 4$가 된다. 이후 4개의 4를 16으로 바꿀 수 있으므로 스퀘어는 총 3번 가능하다. 따라서 이 수열에서 가능한 스퀘어의 최대 횟수는 3이다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. ($1 \le T \le 32$)

각 테스트 케이스의 첫 줄에는 정수 $n$이 주어진다. ($1 \le n \le 50\,000$)

다음 줄에는 $n$개의 정수 $a_1, a_2, \ldots, a_n$이 공백으로 구분되어 주어진다. ($1 \le a_i \le 1\,000\,000\,000$)

다음 줄에는 쿼리의 개수 $Q$가 주어진다. ($1 \le Q \le 50\,000$)

다음 $Q$개 줄의 $i$번째 줄에는 $i$번째 쿼리를 나타내는 두 정수 $l_i$, $r_i$가 공백으로 구분되어 주어진다. ($1 \le l_i \le r_i \le n$)

각 테스트 케이스마다 첫 줄에 "Case #$C$"를 출력한다. 이때 $C$는 테스트 케이스의 번호이다.

다음 $Q$개 줄에는 가능한 스퀘어의 최대 횟수를 출력한다.