GSCANDY - Collecting Candies

no tags 

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 109 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. Combo-x means that he has collected x candies of the same color consecutively. In other words, if he collect a candy and get combo-(x-1) 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 combo-x, 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.
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.

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: 2018-08-27 20:52:47

Awesome DP problem.

nimphy: 2018-05-30 16:19:41

good dp problem!

Rishav Goyal: 2015-06-29 14:34:11

Last edit: 2015-06-29 14:57:20
asshole: 2015-02-05 08:04:38

can anyone give some corner cases ?

Vikneshwar E: 2015-01-29 08:49:31

Nice Problem :)


Added by:jonathanirvings
Date:2014-12-31
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"