There is an unweighted, undirected hidden graph. You are given an integer range from to . There are total of nodes numbered from to . Two nodes have an edge between them if the is greater than .
You have to find the number of the connected components , of this graph and find the size of each component.
An explanation of the unweighted and undirected graph can be found here. An explanation of the connected component can be found here.
The first line of the input consists of the number of test case . Each test case consists of two integers and .
For 40 Points: .
For 100 Points: .
The first line of each test case consists of integer denoting the number of connected components of the graph. Then each of the next X lines consists of the size of each component in sorted order.
Input | Output |
---|---|
2 1 9 2 7 | 4 1 1 1 6 3 1 1 4 |
Hidden graph for the first test case: The greatest common divisor for the following pairs is greater than 1: , , , , , , , , . Each pair of nodes above share a common edge between them. So, there are 3 components consists of 1 node and another component with 6 nodes. |