Вашей компании выдали проект по укладке нового асфальта на трассе длиной \(n\). Вы знаете, что каждый день вы можете либо заменить асфальт на одной единице трассы, либо не заменять.
Перерывы в укладке обусловлены климатом. Климат в вашем регионе периодический: \(g\) дней погода хорошая, и если вы уложите асфальт в эти дни, то покрытие получится высокого качества; далее идут \(b\) дней плохой погоды, и если вы уложите асфальт в эти дни, то покрытие получится низкого качества; далее снова идут \(g\) хороших дней, \(b\) плохих и так далее.
Вы можете быть уверены, что работы по ремонту трассы начнутся в начале хорошего сезона, то есть дни \(1, 2, \dots, g\) — хорошие.
Вас не сильно волнует качество трассы, а потому вы просто хотите, чтобы хотя бы половина трассы имела покрытие высокого качества. Например: если \(n = 5\), то хотя бы \(3\) единицы трассы должны быть высокого качества; если \(n = 4\), то хотя бы \(2\) единицы должны быть высокого качества.
Какое минимальное количество дней необходимо, чтобы отремонтировать всю трассу?
Выходные данные
Выведите \(T\) целых чисел — по одному на набор. Для каждого набора выведите минимальное количество дней, необходимое для ремонта всей трассы, как минимум половина которой должна быть высокого качества.
Примечание
В первом наборе входных данных вы можете укладывать асфальт каждый день, так как \(1, 3, 5\) — хорошие дни.
Во втором наборе вы также можете укладывать асфальт каждый день, так как дни \(1\)-\(8\) — хорошие.