Primes and Queries

You are given a prime number $P$.

Let's define $V(x)$ as the degree of $P$ in the prime factorization of $x$. To be clearer, if $V(x)=y$ then $x$ is divisible by $P^y$, but not divisible by $P^{y+1}$. Also we define $V(0)=0$.

For example, when $P=3$, and $x=45$, since $45=5 \cdot 3^2$, therefore $V(45)=2$.

You are also given an array $A$ with $N$ elements. You need to process $Q$ queries of $2$ types on this array:

• type $1$ query: 1 pos val - assign a value $val$ to the element at $pos$, i.e. $A\_{pos} := val$
• type $2$ query: 2 S L R - print $\displaystyle\sum\_{i=L}^{R}{V(A\_i^S - (A\_i \bmod P)^S)}$.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

The first line of each test case contains $3$ space separated positive integers $N$, $Q$ and $P$ - the number of elements in the array, the number of queries and a prime number.

The next line contains $N$ positive integers $A\_1$, $A\_2$, $\cdots$, $A\_N$ representing elements of array $A$.

Each of the next $Q$ lines describes a query, and contains either

• $3$ space separated positive integers: 1 pos val
• or $4$ space separated positive integers: 2 S L R

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is a list of the answers for each query of type $2$.

• $1 \le T \le 100$
• $2 \le P \le 10^9$
• $P$ is a prime number.
• $1 \le pos \le N$
• $1 \le L \le R \le N$

For at most 10 cases:

• $1 \le N \le 5 \times 10^5$
• $1 \le Q \le 10^5$

For the remaining test cases:

• $1 \le N \le 10^3$
• $1 \le Q \le 10^3$

There will always be at least one query of type $2$.

In Sample Case #1

The first query is a query of type $2$, where $S=3$, $L=3$, $R=4$. Let's calculate the result for this query:

$i=3$, $V(62^3 - (62 \bmod 2)^3)=3$

$i=4$, $V(67^3 - (67 \bmod 2)^3)=1$

$\displaystyle\sum\_{i=3}^{4}{V(A\_i^3 - (A\_i \bmod P)^3)} = 3+1 = 4$

The second query is of type $1$, where we need to assign $69$ to $A\_1$, so our array $A$ now becomes: 69 94 62 67 91.