Suppose I have $M_1,...,M_n$ prime numbers in a specific range $[M_\min,M_\max]$ such that $M_i-1$ is not odd-squarefree ($\exists p^2|M_i-1, p$ odd). Let $n_i=\frac{M_i-1}{2}$. Find all the r-tuples of $n_i$'s such that $(n_{j_1},...,n_{j_r})$ are pairwise coprime. We can assume $r<9$.
Remarks: The brute force method is to simply enumerate all r-tuples and check each one in $O(n^8)$ at worst. I can see that the problem can be reduced in the following way: construct a graph between $n_i,n_j$ iff $\gcd(n_i,n_j)=1$, the problem is to enumerate all cliques of size r. Is there a better way? I also thought of partitioning the set by classes where class $i$ contains the elements whose smallest prime divisor is the $i$-th prime number $p_i$ but this won't affect the complexity...