ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1292. Марсианские космобазы

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Раздался громкий взрыв. На крейсере «Адмирал Бриско», флагмане третьего земного флота, летевшем за подмогой на Сириус, протяжно завыла сирена.
— Капита-ан! — раздался истошный, почти истерический, вопль бортинженера.
— Что это было? Наши повреждения?!!! — почти прокричал командир.
— Капитан! Корабль-разведчик зергов невесть как оказался рядом. Перед тем, как мы его уничтожили, успел взорвать наш левый реактор — левый двигатель и бортовой компьютер выведены из строя. Мы обречены! Нас уничтожат! — кричал обезумевший бортинженер.
Капитан и сам понимал всю серьезность ситуации: до Сириуса им уже не долететь, возвращаться назад было бы полным безумством — наверняка, разведчик успел сообщить координаты крейсера. Эскадрилья лёгких истребителей зергов, как пить дать, уже направляется к ним, и явно не для того, чтобы помогать чинить левый двигатель. Выход один — попытаться дотянуть до следующей космобазы. Космобаза — новое оружие марсиан, союзников землян в войне с зергами, — это подвижный, хорошо обороняющийся и практически неуязвимый космический форт для защиты стратегически важных путей Союза Пяти, куда кроме землян входят марсиане, венерианцы, андромедяне и сирианцы. На каждом таком пути находятся множество космобаз, распложенных особым образом. Каждую космонеделю для конспирации космобазы меняют свое местоположение в соответствии с еженедельно обновляемым Секретным Марсианским Ключом (СМК).
— Позвать ко мне программиста, — прорычал капитан.
Тут появляетесь вы (как вы уже, наверное, поняли, несчастье быть программистом на «Адмирале Бриско» пало на вас).
— Лейтенант, у меня к вам просьба… Нет! Приказ! Вычислить расстояние до базы «Андромеда-Сириус-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-й космобазы.

Пример

исходные данныерезультат
2
4 6 123
7 93 49
18
104
Автор задачи: Денис Мусин
Источник задачи: IX Открытое командное соревнование школьников по программированию (13.03.2004)