You are given a long expression that consists of numbers and operators + and * between them. There are Q queries. In each query you are given two positions A[i] and B[i] in the expression and you need to evaluate the expression between these two positions (inclusive). Because the result could be very large, it should be printed modulo 45 678.

Input

The first line of input contains one positive integer T (1 <= T <= 10), the number of test cases.

The first line of every test case starts with N (1 <= N <= 100 000). In the next line you are given the expression that contains N numbers with operators between them. Each number is between 0 and 45 677. Before and after each operator there is blank space. In the second line you are given Q (1 <= Q <= 100 000), the number of queries. In each of the next Q lines you are given A[i] and B[i] (1 <= A[i] <= B[i] <= N).

Output

For each query, on a separate line, output the evaluation of the expression between the given positions modulo 45 678.

Constraints

Time limit: 5 seconds
Memory limit: 512 megabytes

Examples

input
1
10
5 + 3 * 2 * 7 * 8 * 9 + 6 + 4 * 2 + 3
4
2 5
1 4
1 7
1 10

output
336
47
3035
3046