교통 정기권

자동차를 사면 돈이 많이 들고 정체 때문에 고생한다고 생각한 당신은 대중교통만 이용하기로 했다. 이 도시의 대중교통은 버스와 기차로 이루어져 있고, 요금 규정은 다음과 같다.

1. 버스는 한 번 탈 때마다 $1, 기차는 한 번 탈 때마다 $2를 낸다.
2. 환승 할인은 없다. 버스나 기차를 갈아탈 때마다 표를 새로 산다.
3. 1일 버스 카드는 $3이고, 하루 동안 버스를 횟수 제한 없이 탈 수 있다. 기차 요금은 따로 낸다.
4. 1일 교통 카드는 $6이고, 하루 동안 버스와 기차를 횟수 제한 없이 탈 수 있다.
5. 7일 버스 카드는 $18이고, 7일 동안 버스를 횟수 제한 없이 탈 수 있다. 기차 요금은 따로 낸다.
6. 7일 교통 카드는 $36이고, 7일 동안 버스와 기차를 횟수 제한 없이 탈 수 있다.
7. 30일 버스 카드는 $45이고, 30일 동안 버스를 횟수 제한 없이 탈 수 있다. 기차 요금은 따로 낸다.
8. 30일 교통 카드는 $90이고, 30일 동안 버스와 기차를 횟수 제한 없이 탈 수 있다.

카드는 어느 날에든 살 수 있고, 산 날부터 정해진 일수만큼 연달아 쓴다. 3일에 7일짜리 카드를 사면 3일부터 9일까지 쓴다. 카드는 몇 장이든 살 수 있고, 사용 기간이 서로 겹쳐도 된다. 기록의 마지막 날을 넘기는 카드를 사도 되지만 남는 기간에서 얻는 이득은 없다.

요금 규정이 복잡한 데다 버스와 기차를 며칠에 몇 번씩 탈지 몰라서 당신은 카드를 한 장도 사지 않고 탈 때마다 1회 요금을 냈다. 지금 와서 보니 카드를 샀다면 돈을 덜 썼을 것 같다.

3일 동안의 이용 기록이 다음과 같다고 하자.

카드를 한 장도 사지 않으면 1일에 $1, 2일에 $5, 3일에 $4를 내서 모두 $10을 쓴다. 2일에 1일 버스 카드를 사면 1일에 $1, 2일에 $3, 3일에 $4를 내서 모두 $8을 쓴다. $8이 최솟값이다.

$n$일 동안의 이용 기록이 주어질 때, 요금의 최솟값을 구하는 프로그램을 작성하시오.

입력은 표준 입력으로 받는다. 첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 날의 수 $n$이 주어진다 ($1 \le n \le 10000$). 이어지는 $n$개 줄에는 그날의 버스 탑승 횟수 $a$와 기차 탑승 횟수 $b$가 공백 하나를 사이에 두고 주어진다 ($0 \le a, b \le 100000$).

출력은 표준 출력으로 한다. 각 테스트 케이스마다 요금의 최솟값을 한 줄에 하나씩 출력한다.