package main import ( "bufio" "container/heap" "fmt" "os" "strconv" ) ////pq/////////////////////////////// type Item struct { //value int priority int index int } type PriorityQueue []*Item func (pq PriorityQueue) Len() int { return len(pq) } func (pq PriorityQueue) Less(i, j int) bool { return pq[i].priority > pq[j].priority } func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] pq[i].index = i pq[j].index = j } func (pq *PriorityQueue) Push(x interface{}) { n := len(*pq) item := x.(*Item) item.index = n *pq = append(*pq, item) } func (pq *PriorityQueue) Pop() interface{} { old := *pq n := len(old) item := old[n-1] item.index = -1 // for safety *pq = old[0 : n-1] return item } func (pq *PriorityQueue) update(item *Item, value int, priority int) { //item.value = value item.priority = priority heap.Fix(pq, item.index) } ////nextInt//////////////////////////// var s = bufio.NewScanner(os.Stdin) func next() string { s.Split(bufio.ScanWords) s.Scan() return s.Text() } func nextInt() int { i, e := strconv.Atoi(next()) if e != nil { panic(e) } return int(i) } /////solve/////////////////////////////////////// func solve(l []int) { m := make(map[int]int) //fmt.Println(l) for _, v := range l { m[v] += 1 } //fmt.Println(m) pq := make(PriorityQueue, len(m)) i := 0 for _, p := range m { pq[i] = &Item{ //value: v, priority: p, index: i, } i++ } heap.Init(&pq) var ans int for pq.Len() >= 3 { a := make(map[int]int) ans += 1 for i := 0; i < 3; i++ { item := heap.Pop(&pq).(*Item) a[i] = item.priority - 1 } //fmt.Println(a) for _, p := range a { if p > 0 { item := &Item{ //value: v, priority: p, } heap.Push(&pq, item) } } } fmt.Println(ans) } func main() { var T int fmt.Scan(&T) L := make([][]int, T) for i := 0; i < T; i++ { var N int fmt.Scan(&N) L[i] = make([]int, N) for j := 0; j < N; j++ { //L[i][j] = nextInt() var s int fmt.Scan(&s) L[i][j] = s } } for i := 0; i < T; i++ { solve(L[i]) } }