Convenient Shipments#13104

Convenient Shipments

9 seconds
256 megabytes

A train of wagons stands on the main track of a freight station. The wagons are numbered from to from the locomotive, and the -th wagon carries a_i identical boxes.

The station sends cargo off in shipments. A shipment is a group of consecutive wagons i, i+1, \ldots, j, and all its boxes are packed into containers. All containers used for one shipment must have the same capacity d \ge 2, and every wagon must be packed completely, without leftovers. A group of consecutive wagons is called convenient if it can be sent as one shipment, that is, if there is an integer d \ge 2 such that the number of boxes in each wagon of the group is divisible by . In other words, the group is convenient if and only if \gcd(a_i, a_{i+1}, \ldots, a_j) > 1. A single wagon with a_i \ge 2 boxes forms a convenient group; a wagon with exactly one box does not.

During the day messages of two kinds arrive:

Answer all messages of the second kind.

Input

The first line contains an integer (1 \le t \le 3 \cdot 10^5) — the number of test cases.

The first line of each test case contains two integers and (1 \le n, q \le 3 \cdot 10^5) — the number of wagons and the number of messages. The second line contains integers a_1, a_2, \ldots, a_n (1 \le a_i \le 10^9) — the initial numbers of boxes.

Each of the next lines contains a message in one of the two forms:

  • 1 p x (1 \le p \le n, 1 \le x \le 10^9);

  • 2 l r (1 \le l \le r \le n).

The sum of over all test cases does not exceed 3 \cdot 10^5, and the sum of over all test cases does not exceed 3 \cdot 10^5.

Output

For each message of the second kind print one integer on a separate line — the number of convenient groups inside the given segment. Print the answers in the order in which the messages are given, test case after test case.

Examples

Example 1

Loading
Loading

Note

The figure shows the first test case: every convenient group for the two messages 2 1 5 is drawn as a bar under its wagons.

In the first test case the train is initially 2, 6, 3, 1, 4. A group of wagons from to is written as .

  • Message 2 1 5: the convenient groups are , , , , , , so the answer is . For example, is not convenient because \gcd(2, 6, 3) = 1, and is not convenient because wagon carries one box.

  • Message 2 2 3: the convenient groups are , , , so the answer is .

  • Message 1 4 8: the train becomes 2, 6, 3, 8, 4.

  • Message 2 1 5: the convenient groups are , , , , , , , , so the answer is .

  • Message 2 3 5: the convenient groups are , , , , so the answer is .

In the second test case the train is 2, 2, 3, 3.

  • Message 2 1 4: the convenient groups are , , , , , , so the answer is . No group containing both wagons and is convenient, since \gcd(2, 3) = 1.

  • Message 2 2 3: the convenient groups are and , so the answer is .

In the third test case the train is .

  • Message 2 1 1: the only wagon carries one box, so there are no convenient groups and the answer is .