H. Real Estate Is All Around
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Many people have much money and expect to buy houses, but you are the opposite. You have a lot of houses but not much money. Fortunately, you can predict the future real estate speculation accurately, and you have three "smart" assistants. You can delegate the houses to them and have them help you sell the houses to make a profit.

Your predictions include two types, arranged in chronological order. The following explains the two types of predictions:

  1. Delegate opportunity: you need to specify an assistant and delegate a house worth $$$a_i$$$ to him;
  2. Real estate speculation: the assistants with houses delegated to them will each select a house to sell, and bring you the corresponding profit (note that the profit and the original value of the house may not be the same).

Here are your three "smart" assistants:

Little RedLittle GreenLittle Blue
House to sellEarliest delegated houseHighest value houseLowest value house
Profit given to you after selling a house worth $$$a_i$$$$$$a_i-1$$$$$$a_i-\lceil \frac{a_i}{10} \rceil$$$$$$a_i$$$

Given a prediction sequence of length $$$n$$$ arranged in chronological order, please select the appropriate assistant for all the first type of predictions, so as to maximize the total profit obtained from the second type of predictions, and output this total profit. Please note that after the predictions end, any unsold houses will be wasted and will not bring any profit.

Input

The first line contains an integer $$$T$$$ ($$$1\le T\le 10^4$$$), indicating the number of test cases.

For each test case, the first line contains an integer $$$n$$$ ($$$1\le n\le 200$$$) representing the number of predictions, followed by $$$n$$$ lines, each describing a prediction in chronological order, in the following format:

  • 1 $$$a_i$$$ ($$$1\le a_i\le 10^6$$$), representing the first type of prediction;
  • 2, representing the second type of prediction.

It is guaranteed that $$$\sum n\le 10^4$$$.

Output

For each test case, output a single integer on a new line, representing the maximum profit you can obtain.

Example
Input
2
7
1 40
2
1 30
1 20
1 15
1 1
2
7
1 40
1 30
1 20
1 15
1 1
2
2
Output
102
103
Note

For the first test case, first, delegate the house worth $$$40$$$ to Little Blue, then a real estate speculation occurs, and assistant Little Blue sells the house and brings you a profit of $$$40$$$. After that, you delegate the house worth $$$30$$$ to Little Blue, the house worth $$$20$$$ to Little Red, the house worth $$$15$$$ to Little Green, and the house worth $$$1$$$ to Little Red. In the final real estate speculation, assistant Little Red selects the earliest delegated house worth $$$20$$$, sells it, and brings you a profit of $$$19$$$, Little Blue brings you a profit of $$$30$$$, and Little Green brings you a profit of $$$13$$$, for a total profit of $$$102$$$. It can be proved that this is the most profitable allocation method.

For the second test case, one way to obtain the maximum profit is to delegate the house worth $$$40$$$ to Little Red, $$$30$$$ to Little Red, $$$20$$$ to Little Blue, $$$15$$$ to Little Blue, and $$$1$$$ to Little Blue.