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

Cho xâu ký tự \(s\) bao gồm các ký tự in thường. 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\) để hai ký tự giống nhau đều không kề nhau 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 đưa vào số lượng bộ test \(t\) (\(1 \leq t \leq 100\)).
• Những dòng tiếp theo, mỗi dòng chứa một xâu ký tự \(s\) (\(|s| \leq 10000\)) của mỗi bộ test.

Output

• Đưa ra kết quả mỗi test theo từng dòng.

Example

3
geeksforgeeks
bbbabaaacd
bbbbb

1
1
-1

Cho \(n\) sợi dây với độ dài khác nhau được lưu trong mảng \(a\). Nhiệm vụ của bạn là nối \(n\) sợi dây thành một sợi sao cho tổng chi phí nối dây là nhỏ nhất. Biết chi phí nối sợi dây thứ \(i\) và sợi dây thứ \(j\) là tổng độ dài hai sợi dây \(a_i\) và \(a_j\).

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(n \leq 2 \times 10^6\)).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_i\) (\(1 \leq a_i \leq 10^9\)).

Output

In ra đáp án theo modulo \(10^9 + 7\).

Example

7
2 4 1 2 10 2 3

59

Cho một mảng \(s\) gồm \(2 \times n\) ký tự, trong đó có \(n\) ký tự '[' và \(n\) ký tự ']'. Xâu \(s\) được gọi là viết đúng nếu \(s\) có dạng \(s_2[s_1]\) trong đó \(s_1\), \(s_2\) là các xâu viết đúng. Nhiệm vụ của bạn là tìm số các phép đổi chỗ ít nhất các ký tự kề nhau của xâu \(s\) viết sai để \(s\) trở thành viết đúng. Ví dụ với xâu \(s = "[]][]["\) ta có số phép đổi chỗ kề nhau ít nhất là \(2\).

Input

• Dòng đầu tiên đưa vào số lượng bộ test \(t\) (\(1 \le t \le 100\)).
• Những dòng kế tiếp đưa vào các bộ test. Mỗi bộ test là một xâu \(s\) (\(1 \le |s| \le 10^5\)) viết sai theo nguyên tắc kể trên.

Output

• Một dòng duy nhất in ra kết quả.

Example

2
[]][][
[][][]

2
0