Tiền tố vô hạn

Cho xâu nhị phân $s$ độ dài $n$ chỉ gồm các ký tự 0 và 1. Xây dựng xâu vô hạn $t$ bằng cách nối liên tiếp vô số bản sao của $s$, tức là $t=ssss\dots$. Ví dụ với $s=10010$ thì $t=100101001010010\dots$

Định nghĩa cân bằng của một xâu $q$ là ${\text{cnt}}_{0,q}-{\text{cnt}}_{1,q}$, trong đó ${\text{cnt}}_{0,q}$ và ${\text{cnt}}_{1,q}$ lần lượt là số lần xuất hiện của 0 và 1 trong $q$.

Hãy đếm số tiền tố (kể cả tiền tố rỗng) của $t$ có cân bằng đúng bằng $x$. Nếu số tiền tố thoả mãn là vô hạn thì in ra -1.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $T$ — số test ($1\le T\le 100$).
• Với mỗi test:
  • Dòng đầu chứa hai số nguyên $n$ và $x$ ($1\le n\le {10}^5$, $-{10}^9\le x\le {10}^9$).
  • Dòng thứ hai chứa xâu nhị phân $s$ độ dài $n$.

Tổng $n$ trên tất cả các test không vượt quá ${10}^5$.

Dữ liệu ra

In ra $T$ dòng, mỗi dòng là đáp án cho một test: số tiền tố có cân bằng bằng $x$, hoặc -1 nếu vô hạn.

Ví dụ