32277번 - 스퀘어 게임

문제

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

제한

힌트