hackercupai/hackercup huggingface dataset:
**Note: The only difference between this and [Chapter 1](https://www.facebook.com/codingcompetitions/hacker-cup/2022/round-3/problems/D1/) is that here, you must find the sum of answers for \(K = 1..N\).**

Boss Rob ain’t Som Tawyer, but he can paint a fence alright.

Rob's fence is made of \(N\) wooden stakes, numbered \(1\) to \(N\) from left to right. Initially (at time \(0\)), the \(i\)th stake is of color \(i\). There is a fencepost before stake \(1\) and after stake \(N\), as well as after every \(K\)th stake starting from the left.

Rob has a simple and joyful plan to repaint his fence, consisting of \(M\) moments in time. At time \(i\), he'll repaint all stakes which are color \(A_i\) to color \(B_i\). Doing so, when would be the *first time* that all pairs of stakes not separated by a fencepost have the same color? If it will never occur, consider the answer to be \(-1\).

Rob is still on the _fence_ about the value of \(K\), so please print **the sum of answers over \(K = 1..N\).** Sorry for the pun (we know there is a lot at _stake_ in this round _gating_ the finals). In our de​_fence_, it makes for good _post_-problem content.

# Constraints

\(1 \le T \le 30\)
\(1 \le N, M \le 600{,}000\)
\(1 \le A_i, B_i \le N\)
\(A_i \ne B_i\)

The sum of \(N\) across all test cases is at most \(4{,}000{,}000\).
The sum of \(M\) across all test cases is at most \(4{,}000{,}000\).

# Input Format

Input begins with an integer \(T\), the number of test cases. For the \(i\)th test case, there is first a line containing two space-separated integers \(N\) and \(M\). Then, \(M\) lines follow, the \(i\)th of which contains two space-separated integers \(A_i\) and \(B_i\).

# Output Format

For the \(i\)th test case, output a single line containing `"Case #i: "` followed by a single integer, the sum of answers for each \(K = 1..N\).

# Sample Explanation

The progressions of fences for the first two sample cases are depicted below (with fenceposts depicted for \(K=2\) and \(K=3\) respectively):

{{PHOTO_ID:631752615085471|WIDTH:700}}

In the first case, the answers are \([0, 2, 4, 3, 4]\) for \(K = 1..5\), so we print \(2+4+3+4 = 13\).

In the second case, the answers are \([0, 1, 3]\) for \(K = 1..3\), so we print \(1+3=4\).

In the third case, the fence (with fenceposts depicted for \(K=3\)) progresses as follows:

{{PHOTO_ID:413921204256250|WIDTH:700}}

For \(K = 1..8\), the answers are \([0, 5, -1, 6, -1, -1, -1, -1]\), so we print the sum \(6\).