Travel Card

A car costs a lot of money and traffic congestion makes it worse, so you decided to use public transport only. The public transport system of your city is made up of buses and trains, and the fare rules are the following.

1. Each bus ride costs $1 and each train ride costs $2.
2. There is no free transfer. Every time you change to another bus or train you buy a new ticket.
3. A daily bus card costs $3 and gives unlimited bus rides for one day. Train rides are paid separately.
4. A daily travel card costs $6 and gives unlimited bus and train rides for one day.
5. A 7 day bus card costs $18 and gives unlimited bus rides for seven days. Train rides are paid separately.
6. A 7 day travel card costs $36 and gives unlimited bus and train rides for seven days.
7. A 30 day bus card costs $45 and gives unlimited bus rides for thirty days. Train rides are paid separately.
8. A 30 day travel card costs $90 and gives unlimited bus and train rides for thirty days.

You can buy a card on any day, and it is valid for that many consecutive days counting from the day you buy it. A 7 day card bought on day 3 is valid from day 3 to day 9. You can buy any number of cards and their valid periods may overlap. A card may run past the last day of the log, and the extra days are worth nothing.

The rules looked too complicated and you did not know how often you would ride, so you bought no card and paid a single ride fare every time. Looking back, buying cards would have cost you less.

Suppose your travel log for three days is the following.

With no card you pay $1 on day 1, $5 on day 2 and $4 on day 3, which is $10 in total. If you buy a daily bus card on day 2 you pay $1 on day 1, $3 on day 2 and $4 on day 3, which is $8 in total. $8 is the minimum.

Given the travel log of $n$ days, write a program that computes the minimum total fare.

Your program reads from standard input. The first line contains the number of test cases $T$. Each test case starts with a line containing the number of days $n$ ($1 \le n \le 10000$). Each of the following $n$ lines contains two integers $a$ and $b$ separated by one space, where $a$ is the number of bus rides and $b$ is the number of train rides on that day ($0 \le a, b \le 100000$).

Your program writes to standard output. For each test case, print the minimum total fare on its own line.