약수 게임

Alice와 Bob이 2인용 게임을 하나 만들었다. 먼저 Alice가 1부터 고정된 정수 $n$까지의 범위에서 양의 정수 $k$를 하나 고른다. 그러면 Bob은 ‘$k$가 $m$으로 나누어떨어지는가?’ 형태의 질문을 한다. 여기서 $m$은 양의 정수이다. Alice는 그런 질문마다 ‘예’ 또는 ‘아니오’로 답한다. Bob은 가능한 한 적은 질문으로 Alice가 마음속에 생각한 수를 알아내려고 한다. 여러분의 과제는 Bob 역할을 하는 프로그램을 작성하는 것이다.

$d(n)$을, 주어진 $n$에 대해 Alice가 어떤 $k$를 고르더라도 $k$를 알아내기 위해 해야 하는 최소 질문 수라고 하자. 테스트 케이스에 대한 여러분 프로그램의 답은, $d(n)$번 이하의 질문으로 $k$를 정확히 알아내면 정답으로 간주된다.