East West University is hosting the closing ceremony of EWU CSE Fest 2024. As usual, every student arrived exactly at the starting time of the ceremony. Hence, there is a queue at the entrance of the university. To get everyone inside smoothly, there are \(5\) punch card machines at the entrance. Due to inactivity, the machines were on standby. Each machine takes \(s_i\) amount of time to start working and then takes \(p_i\) amount of time to let one student pass. At most one student can enter using a punch machine at a time. Once a student is inside, the time to enter the ceremony hall and take a seat is negligible.

The challenge is to find out how long the ceremony needs to be delayed so that everyone can get seated. Can you find out the minimum amount of time the ceremony needs to be delayed?

The first line contains a single integer \(t\) \((1 \leq t \leq 10^5)\) — the number of test cases.
The first line of each test case contains a single integer \(n\) \((1 \leq n \leq 10^9)\) — the number of students.
Each of the next five lines describes the five machines. The \(i\)-th line of the five lines contains two integers \(s_i, p_i\) \((1 \leq s_i, p_i \leq 10^9)\) — described in the statement.

For each test case, print a single integer — described in the statement.

Input copy	Output copy
1 10 1 2 2 3 1 3 3 1 4 1	7