# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Hidden Graph

By Peregrine_Falcon · Limits 2s, 512 MB

There is an unweighted, undirected hidden graph. You are given an integer range from $L$ to $R$. There are total of$R-L+1$ nodes numbered from $L$ to $R$. Two nodes $U,V$ have an edge between them if the $GCD(U, V)$ is greater than $1$.

You have to find the number of the connected components $X$, 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.

## Input

The first line of the input consists of the number of test case $T$ $(1 \leq T \leq 10)$.
Each test case consists of two integers $L$ and $R$.

For 40 Points: $(1 \leq L \leq R \leq 10^3)$.
For 100 Points: $(1 \leq L \leq R \leq 10^6)$

## Output

The first line of each test case consists of integer $X$ 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.

## Sample

InputOutput
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.

### Statistics

65% Solution Ratio

MeekgeekEarliest, 4M ago

Deshi_TouristFastest, 0.0s

PIS_ShamiLightest, 1.3 MB

deepGooglerShortest, 511B

Login to submit

### Editorial

We can easily precalculate the prime divisors of each number using SieveofEratosthenesSieve of Erato...

### Related Contests

 National High School Programming Contest 2021 (Senior)Ended 4M ago National High School Programming Contest 2021 (Junior)Ended 4M ago Replay of National High School Programming Contest 2021Ended 4M ago
Toph uses cookies. By continuing you agree to our Cookie Policy.