1139 . 6.握手大會
TopCoder
Tags
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 1
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
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 1
3
6
6
Hints
Problem Source
原TIOJ1139 / 96 TWN Practice Contest 1。NTU Judge(problem 0137)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 33 |
| 2 | 1 | 33 |
| 3 | 2 | 34 |