Vòng Cổ K-Đẹp

Cửa hàng bán $n$ hạt cườm, mỗi hạt có màu là một chữ cái tiếng Anh in thường (từ "a" đến "z"). Bạn muốn mua một số hạt để xâu thành một chiếc vòng cổ.

Một chiếc vòng cổ là một tập hợp các hạt được nối lại thành một vòng tròn. Bạn được phép chọn một tập con bất kỳ của các hạt và xâu chúng theo thứ tự tùy ý.

Một chiếc vòng cổ được gọi là $k$-đẹp nếu khi xoay nó theo chiều kim đồng hồ đi $k$ vị trí thì vòng cổ vẫn giữ nguyên (không thay đổi). Ví dụ, một vòng cổ có độ dài $1$ là $k$-đẹp với mọi $k$, và một vòng cổ mà tất cả các hạt cùng màu cũng là $k$-đẹp với mọi $k$.

Cho các số nguyên $n$, $k$ và xâu $s$ gồm $n$ chữ cái mô tả màu các hạt trong cửa hàng. Hãy tìm độ dài lớn nhất của một chiếc vòng cổ $k$-đẹp có thể xâu được.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số lượng bộ dữ liệu.
• Mỗi bộ dữ liệu gồm hai dòng:
  • Dòng thứ nhất chứa hai số nguyên $n$ và $k$.
  • Dòng thứ hai chứa xâu $s$ gồm $n$ chữ cái tiếng Anh in thường.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên dương là độ dài lớn nhất của chiếc vòng cổ $k$-đẹp có thể xâu được.

Ràng buộc

• $1\le t\le 100$
• $1\le n,k\le 2000$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $2000$.

Ví dụ