As everyone knows, Timur's favorite number is $$$11$$$. Therefore, for his birthday, he asked for a string with the number $$$11$$$. However, when he opened the gift, he found a string $$$s$$$, which was not what he wanted. Totally disappointed, he started to cry, and his parents, wanting to console him, told him that his string had many substrings that were multiples of $$$11$$$. However, they do not know how to count them, and that is why they need your help. A substring is a group of consecutive characters from a string. For example, $$$102$$$ has substrings $$$1, 0, 2, 10, 02$$$, and $$$102$$$, but not $$$12$$$.
Note that substrings can start with $$$0$$$, and for example, the string $$$02$$$ would correspond to the number $$$2$$$. However, it is guaranteed that the first digit of the string $$$s$$$ given to you will never be zero.
The input consists of an integer $$$t$$$ indicating the number of cases. It is followed by $$$t$$$ cases, each consisting of 2 lines. In the first line, there is a number $$$n$$$ indicating the length of the string, and in the second line, there is the string $$$s$$$ representing Timur's number.
Print $$$t$$$ lines, one for each case indicating the number of substrings of $$$s$$$ that are multiples of $$$11$$$.
$$$n \leq 12$$$ (12 points)
$$$n \leq 300$$$ (14 points)
$$$n \leq 2000$$$ (21 points)
$$$n \leq 100000$$$ and all digits of the number are the same (20 points)
$$$n \leq 100000$$$ and no additional restrictions. (33 points)
2 3 121 4 1000
1 6
