Problem Description
Today Zhanyl (sister Zhan as you know) receives a task about set operation. Although she is very good at this task,
but you know she is very lazy so that she wants you to help her write a program to complete this task. Surly
Zhanyl is able to solve this question, but you know, she is just lazy ...
Here is the problem, you are given n numbers, each number i has a value Ai, initially they are in different set.
Following there are m operations/querys.
The following is 5 possible kinds of oprations/querys:
1 u v: Union the set u belongs to and the set v belongs to.
2 u v: Delete u from its original set and add it to the set v belongs to.
3 u x: change the value of u to x. 1<=x<=109
4 u: query how many numbers you can choose most in set which u belongs to, so no three numbers can form a triangle.
5 u l r: query the gcd of the numbers between [l,r] in the set u belongs to, if there is no number between [l,r],you can suppose the answer is -1. 1<=l<=r<=109
Because Zhanyl is a good person, so she guarantee 1<=u,v<=n above.
You need to tell Zhanyl the answer to each query.
Input
The first line of the input is a single integer T which is the number of test cases.Then comes the T test cases .
For each test case, the first line contains two integer n and m, n is the number of set initially, m is the number
of operations/querys.
Following line contains n integers, A1, A2, ... , An, the value of i-th number.
Following m lines, each line is a operation or query.
Note that 1<=n,m<=105, 1<=Ai<=109
Output
For each case,output "Case #X:" in one line first, X is the case number starting from 1. Following you should output all the querys, each query a line.
Sample Input
1
5 5
1 2 3 4 5
1 2 4
5 2 1 5
2 1 4
3 2 3
4 2
Sample Output
Case #1:
2
3