Турнір
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) — кількості матчів і ймовірностей у відсотках.
Вихідні дані
Для кожного тесту на окремому рядку виводиться одне натуральне число — мінімальна кількість шахових партій (врахуйте, що чемпіонат не повинен перетворитися на шаховий турнір).