4351：Digital root

The digital root (also repeated digital sum) of a number is the (single digit) value obtained by an iterative process of summing digits, on each iteration using the result from the previous iteration to compute a digit sum. The process continues until a single-digit number is reached.
For example, the digital root of 65536 is 7, because 6+5+5+3+6=25 and 2+5=7.
The digital root of an interval is digital root of the sum of all numbers in that interval.

Consider a sequence A₁,A₂,A₃……A_n, your task is to answer some queries[l,r]. For each query, tell the biggest five different digital roots among all continuous subintervals of interval[l,r]

In the first line of the input , we have one integer T indicating the number of test cases. (1 <= T <= 10) Then T cases follows. For each test case, the first line is an integer n indicating the length of sequence(1<=n<=100000); following one line containing n integer A_i(0<=A_i<=1000000000); the third line is an integer Q indicating the number of queries(1<=Q<=100000); following Q lines, each line indicating one query [l,r],(1<=l<=r<=n).

For each test case, first you should print "Case #x:" in a line, where x stands for the case number started with 1. Then for each query output a line contains five integer indicating the answers(if the kind of digital root is smaller than five, output -1 to complete). Leave an empty line between test cases.