We will describe an approach that solves this problem in at most $$$3*n+3$$$ queries. The first 3 queries are for getting the counts of A,T,G,C.

We can search for 2 characters at once:

Assume that the queried string is "yyyyyyyy...yyyyxyyyyyyy...yy" (x and y are 2 different characters)

If the similarity count has increased by 1 from "yyyyyyyyyyyyyyyy...y" then the character is x, else, if it has decreased by 1, then it is y.

We search for the first 2 characters with the most count, which will take $$$2*n$$$ queries.

Then we search for the last 2 characters, which will take $$$n$$$ queries at most (since at least $$$n$$$ characters have been searched in the string before).

Complexity: $$$O(n^2)$$$.

Code: https://mirror.codeforces.com/contest/1981/submission/263736407

It is easy to observe that the gcd is <= min, and one popcount operation reduces the min to <= $$$log(a)$$$.

So we can just brute force all gcds from 2 to log(a), note that each element takes $$$O(log^{*}(a))$$$ iterations to be reduced to 1.

Complexity: $$$O(n*log(a)*log^{*}(a))$$$.

Code: https://mirror.codeforces.com/contest/1981/submission/263736978