Школьнику Васе нравятся числа, которые заканчиваются счастливыми для него цифрами k. Поэтому каждый раз, когда он видит какое-нибудь натуральное число n, он сразу пытается подобрать такое d (d ≥ 2), что число n в системе счисления с основанием d заканчивается как можно большим количеством цифр k.

Требуется написать программу, которая по заданным числам n и k найдет такое d, чтобы число n в системе счисления с основанием d заканчивалось как можно большим количеством цифр k.

Ассоциация Тапкодер организует Всемирное парное соревнование сильнейших программистов. К участию в соревновании допущены первые 2^k зарегистрировавшихся участников, которым присвоены номера от 1 до 2^k.

Соревнование будет проходить по олимпийской системе. В первом туре первый участник встречается со вторым, третий с четвертым и так далее. В каждой паре победителем становится участник, первым решивший предложенную задачу, при этом ничьих не бывает. Все победители очередного тура и только они являются участниками следующего тура. В каждом туре пары составляются из участников в порядке возрастания присвоенных им номеров. Соревнование продолжается до тех пор, пока не останется один победитель.

Организаторам стало известно, что некоторые пары участников заранее договорились о результате встречи между собой, если такая встреча состоится. Для всех остальных встреч, кроме n договорных, возможен любой исход.

Некоторые m участников соревнования представили свои резюме в ассоциацию Тапкодер с целью поступления на работу. Организаторов интересует, до какого тура может дойти каждый из претендентов при наиболее благоприятном для него стечении обстоятельств. При этом для каждого участника в отдельности считается, что все недоговорные встречи, в том числе те, в которых он не участвует, закончатся так, как ему выгодно, а все состоявшиеся договорные встречи закончатся в соответствии с имеющимися договоренностями.

Требуется написать программу, которая для каждого из претендентов определяет максимальный номер тура, в котором он может участвовать.