## Problem I: Plants vs. Zombies HD Super Pro

Plants versus Zombies HD Super Pro is a game played not a grid,
but on a connected graph G with no cycles (i.e., a tree).
Zombies live on edges of the tree and chew through edges so that
tree falls apart! Plants can be purchased and placed on vertices
of the tree to protect the tree from falling
apart. It is not possible to plant more than one plant on the
same vertex. A plant protects one or more adjacent edges,
depending on the strength and capabilities of the plant.

The Almanac offers you to buy any of three different types of
plants:

- PEASHOOTERS: These are your first line of defense and can shoot
peas along any
**one** edge (of your choosing) adjacent to the
vertex upon which it is placed. Cost: $100 per plant.
- SPLIT PEAS: These are hard working pea shooters and can shoot
peas along any
**two** edges (of your choosing) adjacent to the
vertex upon which it is placed. Cost: $175 per plant.
- STARFRUIT: Having just visited the dentist, a STARFRUIT is very
upset and shoots stars along all edges adjacent to the vertex
upon which it is placed. Cost: $500 per plant.

Your goal is to protect the tree from the Zombies by having every
edge covered by at least one plant, and doing so spending the
least amount of money. You can buy more than one of each type of
plant, but you can only plant at most one plant on each vertex.
### Input Format

The input starts with an integer T - the number of test cases (T <= 100). T cases follow, each starting with the integer N on the first line, the number of vertices in G (2 <= N <= 10,000). N-1 line follows, each containing two space separated integers *u* and *v* (0 <= u,v <= N-1, u ≠ v) - describing an edge.

### Output Format

For each test case, print on a separate line the minimum cost of protecting the tree, formatted like in the sample output.

### Sample Input

2
2
0 1
3
0 1
1 2

### Sample Output

$100
$175

*In the second case we can put a Split Pea on the vertex 1.*

*Peter Høyer*

**ACPC 2011**