Sum of Divisors in Range

You are given a list of positive integers and several queries. For each query, you must compute the sum of all divisors for each number within the specified range and output the result modulo (10^9+7). The divisor sum (\sigma(n)) of a number (n) is defined as the sum of all positive divisors of (n). For instance, for (n=6), the divisors are (1, 2, 3, 6) and (\sigma(6)=1+2+3+6=12). Your task is to process each query independently and produce the correct output for every query.

inputFormat

Input is read from standard input (stdin) and has the following format:

1. A single integer (n) denoting the number of elements in the list.
2. A line with (n) space-separated positive integers.
3. A single integer (q) denoting the number of queries.
4. (q) lines, each containing two integers (L) and (R) (1-indexed) representing the inclusive range for the query.

outputFormat

For each query, output a single line to standard output (stdout) containing the sum of the divisors of all numbers in the specified range, computed modulo (10^9+7).## sample

5
4 6 8 9 10
2
1 3
2 5

34
58