A Simple GCD Problem (Hard Version)

9
7
1 2 3 4 5 6 7
100 6 12 20 5 2 7
3
67 67 67
1000000000 1000000000 1000000000
6
8 10 10 12 12 14
1 1 1 1 1 1
8
2010 330 550 2 210 385 1001 323
2010 1000 1200 30 500 1000 2000 1000
4
1 2 4 3
1 1 1 1
6
2 3 4 5 1 6
10 15 20 25 5 30
2
1 2
2 100
5
2860 2860 143 9009 9009
2860 2860 1430 9009 9009
3
2 60 60
10 60 60