Given N nodes, each node is labeled with an integer between 1 and 106 (inclusive and labels are not necessarily distinct). Two nodes have an edge between them, if and only if the GCD (Greatest Common Divisor) of the labels of these nodes is greater than 1. Count the number of connected components in the graph. Input First line of the input T (T ≤ 100) denotes the number of testcases. Then T cases follow. Each case consists of 2 lines. The first line has a number N (1 ≤ N ≤ 105) denoting the number of nodes. The next line consists of N numbers. The i-th (1 ≤ i ≤ n) number Xi (1 ≤ Xi ≤ 106) denotes the label of the node i. Output For each case you have to print a line consisting consisting the case number followed by an integer which denotes the number of connected components. Look at the output for sample input for details. Sample Input 2 3 234 6 234566 Sample Output Case 1: 2 Case 2: 2