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.
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.
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:
(2,4), (2,6), (2,8), (4,6), (4,8), (6,8), (3,6), (3,9), (6,9).
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.
Login to submit
We can easily precalculate the prime divisors of each number using SieveofEratosthenesSieve of Erato...