E. Sigma Sigma Pi
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ integers. Your task is to find the value of the expression

$$$$$$ \displaystyle\sum_{l = 1}^{n} \displaystyle\sum_{r = l}^{n} f(\displaystyle\prod_{i = l}^{r} a_i) $$$$$$

where $$$f(x)$$$ denotes the number of divisors of $$$x$$$.

For example, $$$f(6)=4$$$ because $$$6$$$ has $$$4$$$ divisors: $$$1,2,3$$$, and $$$6$$$.

Since the answer can be large, output the answer modulo $$$10^9 + 7$$$.

Input

The first line of input contains an integer $$$t$$$ ($$$ 1 \le t \le 10^4 $$$) — the number of testcases. Description of each testcase follows.

The first line of each testcase contains an integer $$$n$$$ ($$$ 1 \le n \le 10^5 $$$) — the length of the array $$$a$$$.

The second line of each testcase contains a sequence of $$$n$$$ integers $$$a_1, a_2, a_3, \cdots, a_n$$$ ($$$ \bf{1 \le a_i \le 20} $$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all the testcases does not exceed $$$10^5$$$.

Output

For each testcase, print the answer on a separate line.

Example
Input
3
2
12 8
6
1 2 3 4 5 6
5
17 13 20 12 19
Output
22
204
490
Note

In the first test case,

  • Taking $$$l = 1$$$ and $$$r = 1$$$, we have $$$\displaystyle\prod_{i = l}^{r} a_i = 12$$$ and $$$f(12) = 6$$$.
  • Taking $$$l = 1$$$ and $$$r = 2$$$, we have $$$\displaystyle\prod_{i = l}^{r} a_i = 96$$$ and $$$f(96) = 12$$$.
  • Taking $$$l = 2$$$ and $$$r = 2$$$, we have $$$\displaystyle\prod_{i = l}^{r} a_i = 8$$$ and $$$f(8) = 4$$$.

Hence, the answer is equal to $$$6 + 12 + 4 = 22$$$.