Задача М2884‍‍

В Средиземье 1000 графств, в одном из которых находится волшебное Кольцо. Раз в день Маг может выбрать любое подмножество графств и получить от волшебного Камня ответ, есть ли Кольцо в одном из этих графств. Камень может ошибиться, но никогда не ошибается два дня подряд. Маг может совершать данное действие некоторое количество дней, после чего он должен отправить гонцов в некоторые $k$‍‍ графств, в одном из которых наверняка находится Кольцо. При каком наименьшем $k$‍‍ Маг может это сделать?