Efficient Algotithms 2022

Przed nami stoi rząd wiader. Każde wiadro jest idealne - jest to powierzchnia walca bez górnej podstawy. Każdy walec jest więc w pełni scharakteryzowany przez swój promień r_i, oraz wysokość h_i.

Nasze zadanie jest proste. Na początku bierzemy pierwsze wiadro i ustawiamy je przed sobą. Później bierzemy drugie i ustawiamy je (na razie w powietrzu) tak, aby jego oś symetrii pokrywała się z osią symetrii pierwszego walca, po czym spuszczamy. Tak samo postępujemy z kolejnymi wiadrami. Po skończeniu roboty przed nami stoi konstrukcja z wiader. Niektóre wiadra zmieściły się w innych, niektóre nie. Zakładamy, że jedno wiadro „wchodzi" w drugie, jeśli to pierwsze ma mniejszy promień. Zakładamy także, że wszystkie ścianki mają zerową grubość. Twoim zadaniem jest napisanie programu, który dla danych wysokości i promieni kolejnych wiader wyliczy wysokość tak zbudowanej konstrukcji.

Wejście.

W pierwszej linii pliku wejściowego znajduje się liczba naturalna d (1 ≤ d ≤ 10), określająca liczbę zestawów danych, których opisy umieszczone są kolejno po sobie w następnych liniach pliku. Opis pojedynczego zestawu jest następujący: W pierwszej linii znajduje się liczba naturalna n (1 ≤ n ≤ 1 000 000) określająca liczbę wiader. W następnej linii znajduje się 2n liczb całkowitych: r₁, h₁, r₂, h₂ ... r_n, h_n (1 ≤ r_i ≤ 10000, 1 ≤ h_i ≤ 1000). Liczba ri określa promień i-tego wiadra, natomiast hi - jego wysokość.

Wyjście.

Każdemu zestawowi w pliku wejściowym powinna odpowiadać jedna linia pliku wyjściowego. Ta linia powinna zawierać pojedynczą liczbę całkowitą określającą wysokość konstrukcji zbudowanej z wiader podanych w zestawie.

Example

Input:
3
2
20 20 30 30
2
30 30 20 20
4
40 20 20 30 30 20 20 10

Output:
50
30
50

---

In front of us there is a row of buckets. Each bucket is perfect - it is the surface of a cylinder without a top base. Each cylinder is thus fully characterized by its radius r_i, and height h_i.

Our task is simple. First, we take the first bucket and position it in front of us. Later we take the second one and set it (in the air for now) so that its axis of symmetry coincides with the axis of symmetry of the first cylinder, then we let it down. We do the same with the next buckets. When the job is done, there is a construction of buckets in front of us. Some of the buckets fit into others, some do not. We assume that one bucket "goes into" another if the former has a smaller radius. We also assume that all walls have zero thickness. Your task is to write a program that, for given heights and radii of successive buckets, calculates the height of a structure built this way.

Input

The first line of the input contains a natural number d (1 ≤ d ≤ 10), specifying the number of data sets whose descriptions are placed sequentially in the following lines. The description of a single set is as follows: The first line contains a natural number n (1 ≤ n ≤ 1,000,000) specifying the number of buckets. The next line contains 2n integers: r₁, h₁, r₂, h₂ ... r_n, h_n (1 ≤ r_i ≤ 10000, 1 ≤ h_i ≤ 1000). The number r_i specifies the radius of the i-th bucket, while h_i specifies its height.

Output

Each set in the input should correspond to one line of the output. This line should contain a single integer specifying the height of the structure built from the buckets given in the set.

Example

Input:
3
2
20 20 30 30
2
30 30 20 20
4
40 20 20 30 30 20 20 10

Output:
50
30
50