Time Limit: 3000ms

Description

Everyone loves bilibili :), but do you know bilibili numbers?
A bilibili number begins with 2 and is followed by an arbitrary number of 3.
For example, 23, 233, 23333333 are bilibili numbers while 2, 3, 32, 13 are not.
Now, you must play a game about bilibili numbers with me.
You have a array consisting of n positive numbers. And I can perform m operations of two types:
  1. add l r d -- add an integer d to add elements between l and r, inclusive;(1<=l<=r<=n, d>0)
  2. count l r -- tell me how many bilibili numbers there are between l and r, inclusive.
To simplify this game, I will guarantee that there is up to 40 bilibili numbers at any time,
and you only have to calculate 23, 23333 and 233333333:)

Input

On the first line, there's a number T, indicating the number of test cases.

Then T cases follows. In each case:
Line 1: two numbers n, m.(1<=n,m<=100000)
Line 2: n numbers for the array.
Line n+2 - n+1+m: m operations.

Output

For each query, output the anwser.

Sample Input

1
5 3
10 23 233 233333333 23
count 1 5
add 1 5 13
count 1 3

Sample Output

3
1

Author

qw4990