Problem Statement

There are $N$ cards numbered $1$ to $N$. Card $i$ has an integer $A_i$ written on its front side and an integer $B_i$ written on its back side. For every card, the integers written on the front and back sides are different. Initially, all cards are placed face up (front side up).

You can perform the following operation zero or more times.

• Choose two different cards such that the integers written on their currently facing-up sides are equal, and flip both of them simultaneously.

Determine whether it is possible to reach the state where cards $1$ and $2$ are face down (back side up) and all other cards are face up. If it is possible, find the minimum number of operations required.

You are given $T$ test cases; solve each of them.

Constraints

• $1 \le T \le 125000$
• $2 \le N \le 250000$
• $1 \le A_i,B_i \le 2N$ $(1 \le i \le N)$
• $A_i \ne B_i$ $(1 \le i \le N)$
• The sum of $N$ over all test cases in a single input is at most $250000$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Output $T$ lines. The $i$-th line should contain -1 if it is impossible to reach the target state in the $i$-th test case, and otherwise the minimum number of operations required.