In order for any 2 numbers a,b to have gcd(a,b) = 1, there should not share any prime factors. So given a number x, we want to count the numbers that are not multiples of any of x's prime factors. This can be done by inclusion and exclusion by first adding all then subtracting the count of each of the primes. Since some numbers can be multiples of several primes, inclusion and exclusion is used. The problem is now reduced to be storing the frequency of all prime combinations. For example, if the added number is 60, 60 = 2*2*3*5, so we add 1 to the entries: f[2], f[3], f[5], f[2*3], f[2*5], f[3*5], f[2*3*5]. To count the number of coprimes of 60, the answer would be M (total count of numbers on shelf)-(f[2]+f[3]+f[5])+(f[2*3]+f[2*5]+f[3*5])-(f[2*3*5]). It is guranteed that the number of operations per query is small since the maximum number of distinct primes for any input number is 6 with 2^6 combinations.