|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Сложность Бета
Наш очень умный одногруппник Марсел Маданбеков создал новый язык программирования C+=. В C+= целочисленные переменные можно изменять только операцией «+=», которая прибавляет значение справа к переменной слева. Например, если выполнить «a += b», когда a = 2, b = 3, значение a станет равно 5 (значение b при этом не изменится).
Марсел создал программу-прототип с двумя целочисленными переменными a и b, исходно содержащими некоторые положительные значения. Он может выполнить некоторое количество операций «a += b» или «b += a». Марсел хочет протестировать обработку больших целых чисел, поэтому ему нужно сделать значение a либо b строго больше, чем некоторое данное число n. Какое наименьшее количество операций ему необходимо выполнить?
Входные данные
В первой строке записано одно целое число T (1≤T≤100) — количество наборов входных данных.
Каждая из следующих T строк описывает один набор входных данных и содержит три целых числа a,b,n (1≤a,b≤n≤109) — исходные значения a и b, и значение, которое одна из переменных должна превысить, соответственно.
Выходные данные
Для каждого набора входных данных выведите наименьшее необходимое количество операций. Разделяйте ответы переводами строк.
Input:
2
1 2 3
5 4 100
Output:
2
7
Примечание
В первом наборе входных данных мы не сможем за одну операцию записать значение, большее 3, ни в какую переменную. Один из способов сделать это за две операции — выполнить «b += a» дважды.
Для отправки решений необходимо выполнить вход.
|