Mr.A was studying about fractions in his mathematics lecture. He learned that every fraction can be represented in reduced form.

A reduced form of fraction $a/b$ can be represented as $p/q$ such that $gcd(p,q) = 1$ where $gcd$ is greatest common divisor.

For example , reduced form of fraction $2/4$ is $1/2$.

A fraction $a/b$ is called good fraction if its reduced form $p/q$ satisfies the following conditions :

• Both $p$ and $q$ are odd.
• $p\leq q$

For example , some of the good fractions are $(1/3),(2/2),(2/6),...$

but $(2/5),(4/10),(3/1)$ are not good fractions.

Now, Mr.A was given an undirected graph with $N$ nodes and $M$ edges. The given graph does not have any multiple edges or self loops.

Now, task assigned to Mr.A was to find answer for every node $i$ ,

Let $s$ be set of numbered/indexed nodes which are not adjacent to node $i$ .

Calculate number of good fractions $a/b$ where $1\leq a \leq N$ and $1 \leq b \leq N$ such that their reduced form $p/q$  satisfies the following conditions , 

• $q = i$
• $p$ must be element of set $s$ .

Mr. A is stuck in this task, please help him.

Example

Consider n = 3, m = 1.
Edges:

• 2 3

You must determine the output as mentioned above.

The output is 0 0 1.

For node 1: 0

set s is (2,3)

(2/2),(3/3)... are good fractions but in their reduced form, it becomes (1/1) but the numerator is not present in set (s).

For node 2: 0

As q is even

For node 3: 1

set s is (1)

(1/3) is the only good fraction.

Function description

Complete the solve function provided in the editor. This function takes the following 3 parameters and returns the output as mentioned above.

• n: Represents the number of nodes
• m: Represents the number of edges
• edges: Represents the connection between nodes

Input Format:

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

• First line contains $T$ which denotes number of test cases. For each test case,
  • First line contains $N$ and $M$.
  • $M$ lines follow, each contains two numbers $a$ and $b$ denoting edge between them.

Output Format:

For each node $i$ , print the output as mentioned above.

Constraints:

$1\leq T \leq 5$

$1\leq N \leq 100,000\\ 0\leq M \leq min(\frac{N*(N-1)}{2} , 100000)$

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.