There is a transmission system consisting of $N$ compound gears and $M$ chains. Each chain connects two compound gears $u$ and $v$ and provides a gear ratio of $x:y$. This means that if we only consider these two gears, for every $x$ rotations of gear $u$, gear $v$ will rotate $y$ times. A positive gear ratio indicates that if gear $u$ rotates clockwise, gear $v$ also rotates clockwise. A negative gear ratio indicates that if gear $u$ rotates clockwise, gear $v$ rotates counter-clockwise. If the gear ratios of different chains are incompatible, some gears may be unable to rotate. We want to determine whether all $N$ compound gears in the system can rotate simultaneously.

Input

There are multiple test cases. The first line contains an integer $T$, representing the total number of test cases. The following lines contain the $T$ test cases.

The first line of each test case contains two integers $N$ and $M$, representing the total number of gears and the total number of chains, respectively.

The next $M$ lines describe each chain. Each line contains four integers $u$, $v$, $x$, and $y$, indicating that for this specific linkage, gear $u$ rotating $x$ times results in gear $v$ rotating $y$ times. Note that $x$ is a positive integer, and $y$ is a non-zero integer, but $y$ may be negative.

Output

Output $T$ lines, corresponding to each test case. First, output the identifier for the test case as shown in the sample output. Then, output the result: if the $N$ compound gears can operate simultaneously, output Yes, otherwise output No.

Examples

Input 1

2
3 3
1 2 3 5
2 3 5 -7
1 3 3 -7
3 3
1 2 3 5
2 3 5 -7
1 3 3 7

Output 1

Case #1: Yes
Case #2: No

Subtasks

For $30\%$ of the data, $N \leq 10$, $M \leq 18$.

For $100\%$ of the data, $T \leq 32$, $1 \leq N \leq 1\,000$, $1 \leq M \leq 10\,000$, $|x|, |y| \leq 100$.