TopCoder

Thumb 100
tmwilliamlin
我的中文很爛

User's AC Ratio

78.6% (11/14)

Submission's AC Ratio

45.9% (17/37)

Description

有鑑於大家都喜歡握手的個性,Mr.Shake Hand創辦了一個握手社。
該社的成員每個月都有一次的聚會,而每次的聚會大家都拼了命的和其他人握手。
由於握手社成立後大家踴躍加入,所以Mr.Shake Hand幫大家分組,握手大會的時候就先跟自己的組員握手。

今天是握手社第4649次社員聚會,他們在圓桌旁邊坐了下來,圍成一圈。
這次Mr.Shake Hand想要來點不一樣的點子,他說:「每次大家同時握手的時候,手都會交叉,這樣會讓大家很不好握。
「這次我們來點不一樣的吧!不一定要跟自己同組的組員握手,但是每個人都要和另一個人握手,而且手都不可以交叉。」

於是大家就按照Mr.Shake Hand的想法開始握手了。
根據握手禮儀,若A和B握手,那麼B只能全神貫注的跟A握手。
例如以下六個人的握手情況,左邊的方法是合法的,右邊則是不合法的握手。

當然,Mr.Shake Hand還是希望大家能盡量跟同組的人握到手。
請你幫忙算算,在大家同時都要握手的情況下,最多能有多少對同組的握手者呢?

Input Format

輸入檔第一列有一個正整數T,代表測試資料筆數。
每筆測試資料佔兩列,第一列有一個正整數N(1<=N<=1,000)代表圍在圓桌旁的人數,該數字一定是偶數。
第二列有N個正整數,順時針表示了每個人所在的組別編號。第二列的每個數字都介於1到100(包含1和100)之間。

Output Format

對於每組測試資料,請輸出最多同組握手者的對數。//(不是log)

Sample Input

2
6
1 2 2 1 3 3
22
1 7 1 2 4 2 4 9 1 1 9 4 5 9 4 5 6 9 2 1 2 9

Sample Output

3
6

Hints

Problem Source

原TIOJ1139 / 96 TWN Practice Contest 1。NTU Judge(problem 0137)

Subtasks

For Testdata: 0 ~ 0, Score: 33
For Testdata: 1 ~ 1, Score: 33
For Testdata: 2 ~ 2, Score: 34
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 262144
1 10000 65536 262144
2 10000 65536 262144