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:
1 p x — wagon has been reloaded and now carries boxes, that is, a_p becomes equal to ;
2 l r — the dispatcher wants to know how many convenient groups consist only of the wagons l, l+1, \ldots, r, that is, the number of pairs with l \le i \le j \le r such that \gcd(a_i, a_{i+1}, \ldots, a_j) > 1.
Answer all messages of the second kind.
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.
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.
Example 1
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 .