Sharmeen is little girl but familiar with English letters. She is so expert that she is able to cope with any problem related with letters. So her friend Mozahid gives her a challenge to solve an interesting problem related with letters and she easily  solved it. As you are a good programmer can you do the same as Sharmeen?

You are given an string of letters of length n (1 based index). At the beginning all the letters in that string are ‘#’. There exist two types of query:

1. Update X V
2. Query L R V

Update X V: Find d, where d = lowest divisor of X which is greater than 1 and replace all the positions (d^1, d^2, d^3, d^4, …. ), with letter V.

Query L R V: Find how many letter V are in the range of position L to R (inclusive).

There will be q such type of query.

Input

First line contains the input string of length n, which contains only character ‘#’.

Second line of the input is the number of query q.

Then there will be q queries, which can be any of the two types mentioned above.

Output

For each query of type 2 output the number of occurrence of letter V in the range L to R(inclusive).

See the sample input output for better understanding.

Constrain:

1 <= n <= 10^5

1 <= q <= 10^5

2 <= X <= 10^7

1 <= L <= R <= n

‘a’ <= V <= ‘z’

Example

Input:
##########
4
Query 1 5 a
Update 2 a
Query 1 5 a
Query 8 8 a

Output:
0
2
1