쿼리로 보낼 변수 t를 관리하자. t는 1로 초기화함. 일단 쿼리 전 cnt값을 C라고 하고, t를 쿼리로 보낸 뒤 돌아온 cnt값을 C'라 하면, 두가지 경우가 존재할 수 있음.

1. C'<C (이때 C'=C-1일거임)
그냥 t가 n의 LSB (0이 아닌 마지막 자리)와 일치했다는 의미임. t=t<<1로 업데이트하고 넘어가면 됨.

2. C'>=C
t가 n의 LSB와 일치하지 않았음. 그래도 괜찮음. C와 C'에 대한 정보로 n의 LSB가 뭐"였는지" 즉시 알 수 있게 되었음. 그 LSB는 t<<(C'-C+1)일거고, LSB-t를 쿼리로 보내준 뒤, t는 LSB<<1로 업데이트하고 넘어가면 됨.

이렇게 하면 1번 케이스에서는 쿼리 1개로 비트 1개를 확정했고, 2번 케이스에서는 쿼리 2개로 비트 2개 이상을 확정했으니 최악의 경우에도 쿼리는 30개를 넘기지 않음.