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

Ровно N лет назад было построено новое шоссе между двумя крупными городами, представляющее собой один непрерывный участок, проезд по которому был сделан платным на всём его протяжении. Однако эксперимент провалился — только туристы, плохо ориентирующиеся на местности, были готовы платить, чтобы не тратить время. А подавляющее большинство автомобилистов при виде обозначения платной дороги сворачивало в поисках объездного пути.

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

Каждый нечётный год все участки шоссе делят на два новых участка — левый и правый, длины которых находятся в отношении X : Y, причём левый участок на ближайший год делают бесплатным, а правый — платным. Каждый чётный год всё происходит наоборот: участки делят в отношении Y : X, левый участок делают платным, а правый — бесплатным.

Благодаря этой рекламной кампании, администрации удалось существенно увеличить поток машин на платном шоссе за счёт тех, кто начав движение по бесплатному участку, не решался возвращаться назад при виде следующего платного участка. Но не обошлось и без побочных эффектов — по прошествии N лет схема участков шоссе настолько запуталась, что почти никто не знает их точных длин.

Известно, что длину L_k участка с номером k можно получить из суммарной длины шоссе P по формуле L_k = P × (X / 100)^A_k × (Y / 100)^B_k для некоторых целых чисел A_k и B_k. Причём A_k — это количество лет c момента первого разделения участков шоссе, которое участок был бесплатным, а B_k — платным.

Вам необходимо отвечать на множество запросов, содержащих номера участков K_i. Ответом на каждый запрос являются значения A_ki и B_ki, соответствующие участку с номером K_i.