problem is from NEERC 2011 named "gcd guessing game"

you are given number N which is less than or equal to 10000. (1 <= N <= 10000) number X is hidden. (1 <= X <= N) for each query, you can choose any number Y from 1 to N and get gcd(X,Y). at least how many query you need to determine number X?

solution for this problem is to gather all prime numbers from 1 to N and group them so that product of each group does not exceed N. number of group is our answer. let's say this number G.

my question is with strategy above, we can only determine which prime factor does X have. for example if X is (2^3) * (3^5) , we can say X is multiple of 6 but can't tell how many 2 and 3 does X have. so we need additional query to determine it. so there can be a number we can't certain with G queries. how can we prove there are no such numbers?

sorry for my poor english.