Description

小Q正在检查字符串A是否匹配B。两个串被认为是匹配的，当且仅当它们长度相等，并且不存在一个位置i，满足A_i不等于B_i。

但是，小Q戴了原谅帽，他甚至可以原谅字符串！他给了字符串3次机会，如果有不超过3个这样不同的位置i，那么他也会认为两个串匹配。

对于一个字符串S，S[l,r]表示S的[l,r]区间组成的子串。函数occ(A,B)返回A与B中多少个连续子串匹配。

小Q现在有一个下标从1开始的数字串S，他的工作是处理m个操作：

• l r k，对于l到r的每个位置i，将S_i修改为(S_i+k) mod 10。

? l r T，查询occ(T,S[l,r])。

在大量重复的工作之后，小Q感到非常疲惫。请写一个程序，帮助小Q处理这些操作。

Format

Input

第一行包含一个正整数T(1<=T<=15)，表示测试数据的组数。

每组测试数据中，第一行包含两个正整数n(1<=n<=50000)和m(1<=m<=50000)，分别表示字符串S的长度以及操作的个数。

第二行为一个长度为n的十进制数字串S。

接下来m行，每行描述一个操作：

如果是一个修改，那么格式为+ l r k，其中1<=l<=r<=n且1<=k<=9。

如果是一个询问，那么格式为? l r T，其中1<=l<=r<=n，且T也是一个十进制数字串。

输入数据保证每组数据中sum(|T|)<=100000，且不超过4组数据满足min(n,m)>1000。

Output

对于每个询问，输出一行一个整数，即答案。

Samples

1
5 5
01234
? 2 5 1234
? 2 5 1777
? 2 5 9999
+ 1 5 5
? 1 5 56789

1
1
0
1