There exist a graph with nodes that are numbered from 1 to . There exists an edge between two nodes . Now, if divides or vice versa. Node 1 is not connected to any other node.
Find the minimum size of set of nodes such that all the nodes of this graph except node 1 is covered by this set. A node is said to be covered if it is present in this set or there exists at least one node in the set with which it is directly connected, that is, there is an edge between them.
You must cover all the nodes but not the edges.
Input format
Output format
Print the minimum size of set for each query in a separate line.
Constraints
Graph will have following edges
2-4 , 2-6, 3-6.
One possible set S will be = {4,6,5} . |S| = 3
: