Сбой в квантовом тахометре
(Время: 0,5 сек. Память: 32 Мб Сложность: 48%)
На космическом корабле установлен тахометр, который хранит скорость в виде бесконечной десятичной дроби V (в долях световой скорости), где 0 < V < 1. Для передачи по каналу связи значение скорости сначала умножается на коэффициент усиления k (натуральное число), после чего отправляется в виде десятичной записи. Из-за редкой аппаратной ошибки в модуле округления в переданном числе не меняется целая часть, а в дробной части происходит ровно одно искажение: цифры на позициях x и y после десятичной точки меняются местами. Остальные цифры остаются без изменений. Дробная часть может быть бесконечной.
Инженеры перехватили факт передачи и восстановили параметры сбоя x, y, k. Известно, что целая часть результата не изменилась (то есть 0 < kV < 1).
Ваша задача: по заданным x, y, k восстановить исходную минимальную скорость V в виде несократимой дроби p / q или вывести «-1», если такого значения не существует.
Входные данные
В первой строке входного файла INPUT.TXT задано натуральное число Q – количество запросов. Далее в каждой из Q строк по три натуральных числа x, y, k. (1 ≤ Q ≤ 1000; 1 ≤ x < y ≤ 1000; 2 ≤ k ≤ 109).
Выходные данные
В выходной файл OUTPUT.TXT выведите пару чисел p и q на каждый запрос.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2
2 3 9
3 7 14 | 9 8000
9999 26000000 |
Пояснение к примеру
9 / 8000 = 0.001125; 9 × 0.001125 = 0.010125; вторая и третья цифры после запятой поменялись;
9999 / 26000000 = 0.0003845(769230); 0.0003845(769230) × 14 = 0,0053840(769230); третья и седьмая цифры после запятой поменялись.
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
