Cho xâu ký tự \(s\) bao gồm các ký tự in thường và số \(d\). Nhiệm vụ của bạn là kiểm tra xem ta có thể sắp đặt lại các ký tự trong \(s\) để tất cả các ký tự giống nhau đều có khoảng cách là \(d\) hay không? Đưa ra \(1\) nếu có thể sắp đặt lại các ký tự trong \(s\) thỏa mãn yêu cầu bài toán, ngược lại đưa ra \(-1\).

Input

• Dòng đầu tiên chứa số một số nguyên dương \(t\) (\(1 \leq t \leq 100\)) là số lượng bộ test.
• Những dòng sau đó mô tả \(t\) bộ test:
• Dòng đầu tiên chứa số nguyên dương \(d\) (\(1 \leq d \leq \min(100, |s|)\)).
• Dòng thứ hai chứa xâu ký tự \(s\) (\(|s| \leq 10^6\)).

Output

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

2
2
abb
2
aaa

1
-1