Exotic Foods

Traveling through time is exhausting and quickly works up an appetite. Fortunately, every era is full of exotic foods such as dinosaur meat, dodo-bird eggs, and mammoth milk. Unfortunately, the time machine has no room for a refrigerator, so if Tim wants to eat an exotic food he must eat it on the spot. But once he eats, he becomes so full that he cannot eat anything at all during the very next era he visits. Each food has a value that Tim assigns to it, and his goal is to maximize the total value of the foods he actually eats. The order in which he visits the eras is already fixed and cannot be changed. By choosing which foods to eat, what is the maximum total value he can achieve?

The first line contains the number $K$ of data sets. Then follow $K$ data sets, each in the following form. The first line of each data set contains an integer $n$, the number of foods Tim will encounter, with $1 \le n \le 50000$. The next line contains $n$ integers $v_i$ giving the values of the foods, with $1 \le v_i \le 1000$. The order of the $v_i$ is the order in which Tim encounters them.

For each data set, first print Data Set x: on its own line, where $x$ is the data set's number starting from 1. On the next line, print the maximum total value Tim can achieve. Separate consecutive data sets with a single blank line.