# Expression

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 |