K. Divisible by three
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a positive number $$$n$$$ consisting of $$$m$$$ digits, we define $$$f(x, y)$$$ as a number formed by taking all the digits between the $$$x$$$-th and the $$$y$$$-th digit from the left of $$$n$$$, where $$$1 \leq x \leq y \leq m$$$. The task is to determine the number of $$$f(x, y)$$$ that are divisible by $$$3$$$.

Input

First line consists of a number $$$t$$$- The number of test cases.

Next $$$t$$$ lines each consists of two integers $$$m$$$, $$$n$$$ .

$$$1 \leq t \leq 100 $$$

$$$1 \leq m \leq 10^5$$$

Output

Output consists of $$$t$$$ lines. Each of the $$$t$$$ lines should print the number of $$$f(x, y)$$$ that are divisible by $$$3$$$.

Example
Input
5
6 192021
4 1234
1 3
2 34
10 1234560070
Output
7
4
1
1
27