Вы сражаетесь со Змеем Горынычем — со свирепым монстром из славянских легенд!
Изначально у Змея Горыныча \(x\) голов. Вы можете наносить ему \(n\) типов ударов. Если вы нанесете удар \(i\)-го типа, вы уменьшите количество голов Горыныча на \(min(d_i, curX)\), где \(curX\) — текущее количество голов. Но если после этого удара у Горыныча осталась хотя бы одна голова, у него отрастает \(h_i\) новых голов. Если \(curX = 0\), то Горыныч побежден.
Каждый удар можно наносить любое количество раз, сами удары можно наносить в любом порядке.
Например, если \(curX = 10\), \(d = 7\), \(h = 10\), то после удара количество голов станет равным \(13\) (вы отрубаете \(7\) голов, но после этого у Горыныча отрастает \(10\) новых), но если \(curX = 10\), \(d = 11\), \(h = 100\), то после удара количество голов станет равным \(0\) и Горыныч считается побежденным.
Посчитайте минимальное количество ударов для победы над Змеем Горынычем!
Вам нужно ответить на \(t\) независимых запросов.
Выходные данные
На каждый запрос выведите минимальное количество ударов для победы над Змеем Горынычем.
Если Змея Горыныча нельзя победить выведите \(-1\).
Примечание
В первом запросе вы может нанести первый удар (после этого количество голов станет равно \(10 - 6 + 3 = 7\)), а затем нанести второй удар.
Во втором запросе вы можете нанести первый удар три раза подряд — и Горыныч побежден.
В третьем примере вы не можете победить Змея Горыныча.