Турнир
Word-ландия – новая страна, образованная объединением двух древних государств под воздействием внешних угроз. Эти государства теперь являются провинциями Word-ландии, но референдумы по их наименованию ещё не прошли, поэтому они называются Старшая и Младшая Byte-ландии.
Для сплочения населения было решено провести чемпионат между провинциями. В Старшей Byte-ландии национальной игрой являются шахматы, а в Младшей – волейбол. Поэтому чемпионат решили провести по шахболу. Чтобы не затягивать чемпионат, объединённое правительство решило провести ровно К матчей. Каждый матч – это либо партия в шахматы, либо волейбольный матч. Победитель в матче получает одно очко в зачёт чемпионата, в случае ничьей в шахматной партии обе провинции получают по 0.5 очка.
Правительство заинтересовано в том, чтобы в чемпионате "победила дружба", то есть провинции набрали одинаковое количество очков. Поэтому высокие чины обратились к вам с просьбой определения минимального количества шахматных партий в чемпионате, чтобы разность математических ожиданий набранных провинциями очков была минимальна.
За долгую историю Мировых чемпионатов известно, что Старшая Byte-ландия выигрывает в шахматы у Младшей с вероятностью p_1 и проигрывает в волейбол с вероятностью p_2. Ничья в шахматах достигалась с вероятностью p_3.
Примечание: Математическое ожидание - среднее значение случайной величины в теории вероятностей. Для дискретной случайной величины Х с законом распределения P(X = x_i) = p_i математическим ожиданием называется сумма парных произведений всех возможных значений случайной величины на соответствующие им вероятности, т.е.
Входные данные
В первой строке содержится натуральное число – количество тестов. Описание каждого теста состоит из четырёх целых чисел К (1 < K ≤ 10^16), p_1, p_2, p_3 (0 ≤ p_1, p_2, p_3 ≤ 100) – количества матчей и вероятностей в процентах.
Выходные данные
Для каждого теста на отдельной строке выводится одно натуральное число – минимальное количество шахматных партий (учтите, что чемпионат не должен превратиться в шахматный турнир).