Mùa đông lạnh lẽo đã tới rồi. Chúng mình xin được chúc tất cả các bạn nam đang làm contest này sẽ có người yêu, đừng như shiba trong chuỗi bài này nhé!

Nổi danh đã lâu trong giới lập trình thi đấu nhưng mà là "ao hồ", Trần Thanh Nguyên - còn được biết đến với shiba - là một chàng trai với cơ bụng sáu múi, cao mét tám. Có thể nói là mẫu chồng quốc dân của chị em. À đó là Trần Thanh Nguyên nào chứ shiba này là một chàng trai học công nghệ thông tin bình thường. Trước kia, cậu ấy có một cô bạn gái cực kì xinh gái, nhưng đã không giữ được cô ấy do không thực sự xuất sắc lắm ~nói thẳng ra là do lúc đó anh ta quá nghèo~. Giờ đây đã khác, tuy shiba có tất cả, nhưng giống như lời bài hát nào đó, "chúng ta sau này, chẳng có chúng ta sau này", có tất cả nhưng lại không có em. Chính vì vậy, cậu ấy rất nặng tình với "người yêu cũ" của mình, đó là cậu ấy nói vậy, còn người đời như _minhduc hay Flower_On_Stone thì lại cho là "luỵ", "nhớ" người yêu cũ.

Ngày \(19/11\) năm nay, shiba không có ai chúc mừng ngày Quốc tế Đàn ông, cậu ấy lại nhớ ngày xửa ngày xưa, người ấy đã chúc cậu ấy ngày \(19/11\) vui vẻ như thế nào. Và cậu nhớ lại kỉ niệm với cô ấy. Để hồi tưởng lại, cậu ấy quyết định hồi tưởng từ ngày bắt đầu tán cô ấy.

shiba đã chọn cách tán gái mà đa phần các chàng trai hay làm, đó là tặng sữa Milo cho cô bạn kia. Để nhắc mình nhớ về ngày hôm ấy có tặng cô bạn của mình sữa hay không, cậu ấy sẽ ghi số \(1\) hoặc \(0\) vào nhật kí của mình, biểu diễn cho ngày hôm ấy cậu ấy có hay không mua sữa cho cô bạn của mình. Lâu dần, việc này đã biến cuốn nhật kí của shiba thành một xâu nhị phân \(s\). Việc tán cô bạn đã tốn mất \(n\) ngày của shiba, nên xâu nhị phân đó có độ dài là \(n\).

Giờ đây, chỉ còn mình shiba ngồi lại, cậu ấy nhớ lại những kỉ niệm mua sữa cho cô ấy, và cậu ấy nhận thấy, không biết có phải trùng hợp ngẫu nhiên hay không, nếu như từ ngày \(l\) tới ngày \(r\) (\(l \le r\)), biểu diễn thập phân của đoạn đó đúng bằng \(r-l+1\) thì cô ấy sẽ cực kì vui vẻ và cậu ấy coi đây là một quãng đẹp. Nói cách khác, gọi \(f(l,r)\) là giá trị một số nguyên biểu diễn dưới dạng xâu nhị phân của xâu \(S\) được cắt ra từ vị trí \(l\) đến \(r\) của xâu \(s\), nếu \(f(l,r) = r-l+1\) thì đây sẽ được coi là một quãng đẹp. Cậu ấy tự hỏi, quãng thời gian đó, cô ấy đã vui vẻ được bao nhiêu lần, cậu ấy đã tạo ra được bao nhiêu quãng đẹp. Các quãng đẹp nếu đè lên nhau hoặc chứa nhau vẫn được coi là hai quãng đẹp riêng biệt.

Yêu cầu: Tính số quãng đẹp mà shiba đã tạo ra.

Input

• Dòng đầu tiên chứa một số nguyên \(\phi\) - số thứ tự của subtask chứa test đó.
• Dòng thứ hai chứa một số nguyên dương \(n\) (\(n \le 5 \times 10^5\)).
• Dòng thứ ba chứa một xâu nhị phân \(s\) độ dài \(n\).

Output

• Một dòng chứa một số nguyên là kết quả bài toán.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): xâu \(s\) chỉ chứa một loại kí tự.
• Subtask \(2\) (\(10\%\) số điểm): \(n \le 50\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 10^3\).
• Subtask \(4\) (\(15\%\) số điểm): xâu được tạo thành từ một xâu con lặp lại nhiều lần, độ dài xâu con đó không vượt quá \(30\) (*).
• Subtask \(5\) (\(20\%\) số điểm): \(n \le 10^4\).
• Subtask \(6\) (\(25\%\) số điểm): không có ràng buộc gì thêm.

Example

2
4
0110

4