Наборы без общего делителя

Сколько существует непустых наборов чисел из списка, наибольший общий делитель которых равен единице? Набор из одного числа имеет наибольший общий делитель, равный самому числу.

В первой строке число $n$ от $1$ до $20$. Во второй — $n$ чисел от $1$ до $10^9$.

Одно число.

Наибольший общий делитель удобно накапливать по ходу рекурсии: он не увеличивается, а как только стал единицей, дальше уже не изменится.