Возвращаясь из школы домой, Петя каждый раз обращал внимание на надпись на заборе «1 + 1 = 10» и удивлялся очевидной его неправоте. Но однажды его осенило, что это равенство верное, если рассматривать его в двоичной системе счисления. Его настолько поразила эта идея, что он решил непременно придумать свои три числа так, чтобы сумма первых двух была равна третьему в некоторой системе счисления.

Теперь он перебирает тройки чисел, которые, на его взгляд, достойны находиться на заборе. Петя выбирает числа A, B, C, записывающиеся десятичными цифрами, и дальше пытается найти основание системы счисления K, в которой равенство A + B = C оказалось бы верным. Петя рассматривает системы счисления с основанием от 2 до бесконечности.

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

Этим летом у бабушки был большой урожай яблок. Она собрала яблоки в корзину и отдала своим \(K\) внукам.

Первый внук взял из корзины половину всех яблок и еще \(a_1\) яблоко (если количество яблок не делилось на два, то результат деления на два он мог округлить как в большую сторону, так и в меньшую). К примеру, если в корзине было 7 яблок и \(a_1 = 1\), то он мог взять либо 4, либо 5, а если было 6 яблок и \(a_1 = 1\), то он взял ровно 4.

Второй внук взял половину от всех оставшихся яблок и ещё \(a_2\) (если яблок было нечетное количество, то он также мог округлить половину как в большую, так и в меньшую сторону). И так далее, \(K\)-ый внук взял половину яблок, оставшихся после \(K - 1\) внука, и ещё \(a_k\). В итоге в корзине ничего не осталось.

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