SubString Divide
Tag(s):

## Implementation, Medium, Simple-math

Problem
Editorial
Analytics

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$

SAMPLE INPUT
3
1
8
2
88
3
888

SAMPLE OUTPUT
1
3
5

Explanation

For the first case the only substring is (1,1).

For Second case (1,1),(1,2),(2,2).

For third case (1,1),(1,2),(2,2),(2,3),(3,3).

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

January Easy '17

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Sorting
• Math > Combinatorics
• Data Structures > Advanced Data Structures
• Algorithms > Greedy Algorithms
• Math > Probablity