divnr

"legit checker-ul e imposibil la asta"

Ei bine, Traian mai avea nevoie de probleme pentru concurs, deci s-a gândit să o dea pe asta.

Cerință

Traian s-a gândit la $t$ șiruri de câte $n$ numere (pentru fiecare șir, numărul $n$ nu este neapărat același) și s-a mai gândit și la un număr $m$ pentru fiecare șir (din nou, $m$ nu este neapărat același peste tot). El vrea să-i spuneți un număr care este divizibil cu fiecare număr din șir și are exact $m$ cifre.

Date de intrare

Pe prima linie se va afla numărul $t$, reprezentând numărul de șiruri. Pe a $2 \cdot i$-a linie se vor afla numerele $n$ și $m$. Pe a $2 \cdot i + 1$-a linie se vor afla cele $n$ numere din șir.

Restricții și precizări

• $1 \leq n \leq 2 \cdot 10 ^ 5$
• $1 \leq m \leq 10 ^ 5$
• Suma numerelor $n$ nu depășește $2 \cdot 10 ^ 5$
• Suma numerelor $m$ nu depășește $10 ^ 5$
• Numărul căutat există pentru oricare din cele $t$ șiruri.
• Notăm șirul cu $a$
• $1 \leq a_i \leq 10 ^ 9 \ (1 \leq i \leq n)$
• $1 \leq a_1 \cdot a_2 \cdot ... \cdot a_n \leq 10 ^ 9$

Exemplul 1

stdin

9
4 11
113 158 170 96 
5 10
22 18 6 30 6 
11 9
4 6 5 4 5 3 6 4 5 4 3 
6 11
28 9 9 25 6 17 
3 10
565 623 621 
11 9
2 4 2 3 3 5 4 3 4 4 6 
3 10
920 274 410 
10 11
3 1 5 7 1 3 5 2 4 7 
4 9
30 90 40 26 

stdout

10052516160
6000005880
100000020
80000272800
1092944475
900000180
3007566480
50000000400
100002240

Explicație

Nuj, verfică-le!