A solution that doesn't make use of the max number being 10,000 is using inclusion-exclusion principle. Because when we take the sets of K that have a gcd divisible by 2 and the sets of K that have a gcd divisible by 3, you count twice the ones with a gcd divisible by 6, so you have to subtract those. It's similar to a solution to this problem: https://open.kattis.com/problems/coprimeintegers