Раздался громкий взрыв. На крейсере «Адмирал Бриско», флагмане третьего земного флота, летевшем за подмогой на Сириус, протяжно завыла сирена.

— Капита-ан! — раздался истошный, почти истерический, вопль бортинженера.
— Что это было? Наши повреждения?!!! — почти прокричал командир.
— Капитан! Корабль-разведчик зергов невесть как оказался рядом. Перед тем, как мы его уничтожили, успел взорвать наш левый реактор — левый двигатель и бортовой компьютер выведены из строя. Мы обречены! Нас уничтожат! — кричал обезумевший бортинженер.

Капитан и сам понимал всю серьезность ситуации: до Сириуса им уже не долететь, возвращаться назад было бы полным безумством — наверняка, разведчик успел сообщить координаты крейсера. Эскадрилья лёгких истребителей зергов, как пить дать, уже направляется к ним, и явно не для того, чтобы помогать чинить левый двигатель. Выход один — попытаться дотянуть до следующей космобазы. Космобаза — новое оружие марсиан, союзников землян в войне с зергами, — это подвижный, хорошо обороняющийся и практически неуязвимый космический форт для защиты стратегически важных путей Союза Пяти, куда кроме землян входят марсиане, венерианцы, андромедяне и сирианцы. На каждом таком пути находятся множество космобаз, распложенных особым образом. Каждую космонеделю для конспирации космобазы меняют свое местоположение в соответствии с еженедельно обновляемым Секретным Марсианским Ключом (СМК).

— Позвать ко мне программиста, — прорычал капитан.

Тут появляетесь вы (как вы уже, наверное, поняли, несчастье быть программистом на «Адмирале Бриско» пало на вас).
— Лейтенант, у меня к вам просьба… Нет! Приказ! Вычислить расстояние до базы «Андромеда-Сириус-4»! Вот необходимые вам данные: СМК = 6, номер базы = 4, расстояние от предыдущей базы = 123 космомили.
— Есть! — отвечаете вы и бежите писать программу для расчёта нужного расстояния. Благо алгоритм расстановки марсианских космобаз не является ни для кого секретом. Он состоит в следующем: первая космобаза располагается на расстоянии, равном СМК от одного из концов пути (в данном случае — Сириуса). Вторая база располагается на расстоянии F(СМК) от первой, где F — это Секретная Марсианская Функция (СМФ), вычисляющаяся как сумма кубов цифр в десятичной записи своего аргумента (к примеру, F(12)=9). Третья — на расстоянии F(F(СМК)) от второй и так далее. Если x — расстояние от (i − 1)-й до i-й базы, то расстояние от i-й до (i + 1)-й базы равно F(x). «Что за чушь?» — спросит внимательный читатель и будет прав. А что ещё может прийти в голову этим пушистым кроликам — марсианам?

Ваш корабль находится между (N − 1)-й и N-й космобазами на расстоянии L от (N − 1)-й космобазы. Ваша программа должна, зная N, K (Секретный Марсианский Ключ) и L, выдать расстояние от вашего корабля до N-й космобазы. Ах да, значение СМК всегда кратно трём — у марсиан вообще все числа кратны трём.

В первой строке находится число T (2 ≤ T ≤ 33333) — количество тестов для вашей программы. Далее следуют T строк, в каждой из которых находятся 3 целых числа: N (2 ≤ N ≤ 33333), K (3 ≤ K ≤ 33333) и L (L ≥ 1).

T строк, в каждой — соответствующее расстояние от вашего корабля до N-й космобазы.