스퀘어 게임

$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$개 줄에는 가능한 스퀘어의 최대 횟수를 출력한다.