GSCANDY  Collecting Candies
Jonathan Irvin Gunawan is a very handsome living person. You have to admit it to live in this world.
To become more handsome, Jonathan the Handsome have to collect candies (no relation, indeed). In front of him, there are N candies with different level of sweetness. Jonathan will collect the candies one by one. Jonathan can collect any number of candies, but he must collect the candy in the increasing order of level of sweetness (no two candies will have the same level of sweetness).
Every candy has their own color, which will be represented by a single integer between 0 and 10^{9} inclusive.
If Jonathan collects the first candy, or a candy that has different color with the previous candy he take, he will get 1 point.
If Jonathan collects the candy that has the same color with the previous candy, he will get a combo. Combox means that he has collected x candies of the same color consecutively. In other words, if he collect a candy and get combo(x1) and he collect a candy with the same color again, he will get combo(x). And then if he collects a candy with different color, the combo will vanish and back to combo 1.
(Note : previous candy means the last candy he take)
Every time he get combox, he will get x points. Jonathan wants to count how many maximum total points he can get. You are a fan of Jonathan the Handsome have to help him.
Input
The first line consists of a single integer T, indicating the number of testcases.
For every testcase, the first line consists of a single integer N (1 ≤ N ≤ 1000).
The next line consists of N integers, representing the color of the candy given in the increasing level of sweetness, separated by a single space.
Output
For every case, output a single integer consist of the maximum total points Jonathan can get.
Example
Input: 2 4 1 1 2 1 4 1 2 3 1
Output: 6 4
Explanation
In the first sample, Jonathan chooses not to take the candy with color 2, as he will lose the combo. In the second sample, he will get a maximum total points if he take all of the candies.
hide comments
DOT:
20180827 20:52:47
Awesome DP problem. 

nimphy:
20180530 16:19:41
good dp problem! 

Rishav Goyal:
20150629 14:34:11
Last edit: 20150629 14:57:20 

asshole:
20150205 08:04:38
can anyone give some corner cases ? 

Vikneshwar E:
20150129 08:49:31
Nice Problem :) 
Added by:  jonathanirvings 
Date:  20141231 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Jonathan Irvin Gunawan, used in TOKI OpenContest May 2012, as "Ambil Batu" 