Cho xâu ký \(S\) tự chỉ gồm các chữ cái in hoa. Ta gọi giá trị của xâu \(S\) là tổng bình phương số lần xuất hiện mỗi ký tự trong \(S\). Hãy tìm giá trị nhỏ nhất của xâu \(S\) sau khi thực hiện \(K\) lần loại bỏ ký tự.

Input

• Dòng đầu tiên đưa vào số lượng bộ test \(T\) (\(1 \leq T \leq 100\)).

• Những dòng kế tiếp đưa vào các bộ test. Mỗi bộ test gồm \(2\) dòng:

• Dòng đầu tiên là số \(K\) (\(1 \leq K \leq 1000\));

• Dòng thứ hai là một xâu ký tự \(S\) (\(1 \leq \text{length}(S) \leq 10000\)) (\(\text{length}(S)\) là độ dài của xâu \(S\)).

Output

• Gồm \(T\) dòng, dòng thứ \(i\) là kết quả của test thứ \(i\).

Example

2
2
ABCCBC
2
AAAB

6
2