First of all, K is large but the range of n is small (<=32767 and is prime);
So we can process the query with same n at the same time.

And use brute-force method;

Note if there are solutions there are exacly two solutions.

x and n-x ((n-x)^2=x^2(mod n));

very nice :)

Can you explain me that better, I don't understand your idea.