#586 Pi Problem

Statement

Statement language

For positive integers $a,b$ , define $\mathrm{rep}(a,b)$ as the integer formed by concatenating $b$ copies of the decimal representation of $a$ . For example, $\mathrm{rep}(2,3)=222$ and $\mathrm{rep}(31,4)=31313131$ .

You are given a sequence of positive integers $A_1,A_2,\cdots,A_N$ . Find the value of the following expression modulo .

\prod_{1\leq i<j\leq N}\mathrm{rep}(A_i,A_j)

Input

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the required remainder on one line.

Constraints

$1 \leq T \leq 10\,000$ .
$2 \leq N \leq 200\,000$ .
$1 \leq_{}$ ().

Subtasks

#	Score	Constraints
1	11	$N=2$ , $A_i\leq5$ ( $1\leq i\leq N$ ), and the sum of over all test cases is at most .

Samples

Input

3
2
2 3
3
1 2 1
2
998244353 1

Output

222
22
0

The first product is $\mathrm{rep}(2,3)=222$ . The second is $\mathrm{rep}(1,2)\cdot\mathrm{rep}(1,1)\cdot\mathrm{rep}(2,1)=11\cdot1\cdot2=22$ .