Ramesh and Pramesh were chilling on a fine Sunday afternoon. Pramesh was a maths geek while Ramesh had amazing love for strings. Both of them couldn't control themselves and decided to have some fun. Ramesh knew that Pramesh won't like his string if it contained any alphabets in it. So Ramesh decided to give Pramesh a string consisting of only digits. Pramesh was initially happy seeing the string. Later Ramesh asked Pramesh a question which left him baffled.

He asked Pramesh to tell him the count of substrings in the given string which are divisible by 8 and not by 3. Pramesh is finding it hard to answer this. So he turns to you for help. Help Pramesh in answering this.

Input:

The first line contains an integer T indicating the number of Testcases.

Each testcase consists of 2 lines.

First line contains an integer K that denotes the length of string.

Second lines contains the K-length string.

Output:

For each testcase output in a separate line the number of substrings satisfying the given condition.

Constraints :

T <= \(10\)

Length Of String <= \(10^5\)