Задача A. Турникеты в метро

Автор:Russian Code Cup 2015   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

При каждом проходе через турникет высвечивается, сколько еще дней карта может быть использована (включая текущий день). Но, к сожалению, табло, на котором это количество дней отображается, может показывать только однозначные и двузначные числа. Если же в отображаемом числе хотя бы три цифры, на табло покажется число 99. Например, если на карте осталось 5 дней, то на турникете покажется число 5, если 12 дней, то число 12, а если 123 дня, то на турникете покажется число 99. Если на карте остается 0 дней, она становится неактивной и по ней больше нельзя проходить через турникет.

Сейчас у Васи на карте осталось a дней, а у Пети — b. Они каждый день ездят на метро и каждый день смотрят на числа, которые отображаются на турникете. И им стало интересно: через сколько дней в первый раз число на турникете у одного из них будет ровно в k раз больше, чем число на турникете у другого. Помогите друзьям выяснить ответ на этот вопрос.

Формат входного файла

Первая строка входных данных содержит одно число t — количество тестов. Следующие t строк содержат по тесту каждая. Каждый тест задается тремя целыми числами: a, b, k — количество оставшихся дней на карточках у Васи и Пети и требуемое отношение.

Формат выходного файла

Для каждого набора данных выведите единственное число: через сколько дней у одного из друзей на турникете будет показано в k раз больше поездок, чем у другого. Если такого не произойдет до того дня, когда у одного из друзей карта станет неактивной, выведите -1.

Ограничения

1 ≤ t ≤ 100000

1 ≤ a, b ≤ 2·109

1 ≤ k ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5
2 1 2
100 99 2
17 13 10
3 3 1
1 1 2
0
98
-1
0
-1

0.077s 0.015s 13