Cho xâu ký tự S bao gồm các ký tự in hoa [A, B, ...,Z]. Ta định nghĩa 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 xâu. Ví dụ với xâu S[] = "AAABBCD" ta có F(S) = 3^2 +2^2 +1^2 + 1^2 = 15. Hãy tìm giá trị nhỏ nhất của xâu S[] sau khi loại bỏ K ký tự trong xâu.

Đầu vào: Dòng đầu tiên đưa vào số lượng test T. Mỗi test được tổ chức thành 2 dòng, Dòng thứ nhất ghi lại số K. Dòng thứ 2 ghi lại xâu ký tự S[] có độ dài không vượt quá 10^6.

Ràng buộc: T≤100; 1<=K<=10^6; 1<=len(S)<=10^6; Xâu S chỉ bao gồm các kí tự in hoa hoặc in thường.

Đầu ra: Đưa ra giá trị nhỏ nhất của mỗi test theo từng dòng.

Input:

2
0
АВСС
1
АВСС

Output: