gCube (Small)

$D$차원 정육면체는 길이가 모두 같은 $D$개의 차원으로 이루어진다. $D$는 아무 양의 정수나 될 수 있어서, 1차원 정육면체는 선분이고 2차원 정육면체는 정사각형이며 4차원 정육면체는 초입방체다. $D$차원 직육면체도 차원이 $D$개지만 각 차원의 길이는 서로 다를 수 있다.

$N$차원 직육면체가 주어진다. 차원에는 순서대로 $0, 1, 2, \ldots, N-1$번이 붙어 있고, $i$번 차원의 길이는 $a_i$다. 다음 형태의 질의를 $M$개 처리하자.

1. $L_i$번 차원부터 $R_i$번 차원까지 연속한 차원을 모두 고른다.
2. 고른 차원으로 $D$차원 직육면체를 만든다. 이때 $D = R_i - L_i + 1$이다. 예를 들어 $L_i = 3$이고 $R_i = 6$이면 3, 4, 5, 6번 차원으로 4차원 직육면체를 만든다.
3. 이 직육면체를 부피가 정확히 같은 $D$차원 정육면체로 바꾸고, 그 정육면체의 한 변 길이를 구한다.

한 테스트 케이스의 질의는 모두 같은 $N$차원 직육면체를 사용한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에는 차원의 개수 $N$과 질의의 개수 $M$이 주어진다. 둘째 줄에는 차원의 길이 $a_0, a_1, \ldots, a_{N-1}$이 순서대로 주어진다. 이어지는 $M$개의 줄에는 $i$번째 질의가 사용할 차원의 범위 $L_i$와 $R_i$가 주어진다.

각 테스트 케이스마다 먼저 "Case #x:"를 한 줄에 출력한다. x는 1부터 시작하는 테스트 케이스 번호다. 그다음 $M$개의 줄에 걸쳐 $i$번째 줄에 $i$번째 질의의 한 변 길이를 출력한다.

질의의 답은 $D = R_i - L_i + 1$일 때 $\left(\prod_{j=L_i}^{R_i} a_j\right)^{1/D}$이다. 정확한 값을 소수점 아래 아홉째 자리에서 반올림해 소수점 아래 아홉 자리까지 출력한다. 이 거듭제곱근은 대개 무리수이고 곱은 $10^{90}$까지 커지므로, 아홉째 자리 숫자가 맞을 만큼 정밀하게 계산해야 한다. 소수점 앞에는 숫자를 적어도 한 개 출력하고, 양수 부호는 출력하지 않는다.

• $1 \le T \le 100$
• $1 \le N \le 10$
• $1 \le M \le 10$
• $1 \le a_i \le 10^9$
• $0 \le L_i \le R_i < N$