## OVGDEL - Good Elements

You are given a sequence consisting of integers a_{1}, a_{2}, a_{3}, …, a_{n}. Any element a_{i} is called good if there exists another element a_{j} in the sequence (i≠j) such that a_{j} is a non-negative power of a_{i}. In other words a_{i} is called **good** if there exists an element a_{j} where i≠j and a_{j}=a_{i}^{k} for some k>=0.

For example, consider the following sequence: [2, 4, 4, 6, 3, 8]. This sequence contains **3** good elements. The **1st**, **2nd** and **3rd** elements are good.

1st element “2” is good because there exists “4” and “8” in the different positions of the sequence which are non negative power of “2” (2^{2}=4, 2^{3}=8). 2nd element “4” is good because there exists another “4” in a different position of the sequence which is a non-negative power of “4” (4^{1}=4). Same applies for the 3rd element.

Given the sequence, now you have to find out total number of good elements in the sequence.

### Input

The first line contains an integer t denoting the number of test cases.

For every test case the first line contains the integer n the length of the given sequence. The second line contains the sequence of integers a[1], a[2], a[3], …, a[n].

### Constraints

1<=t<=10

1<=n<=10^{4}

1<=a_{i}<=10^{6}

### Output

For each test case print the case number followed by the result in a single line according to the following format "Case X: R" (without quotes), where X denotes the case number and R denotes the result. See the sample for further clarification.

### Example

Input:3

6

2 4 4 6 3 8

2

1 2

2

10 100

Output:Case 1: 3

Case 2: 1

Case 3: 1

[ This Problem Orginally Contributed byHafiz Al Masud Ovi]

Added by: | Avik Sarkar |

Date: | 2018-07-14 |

Time limit: | 1s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All |

Resource: | Own |