Little Cyan Fish มี $m$ ลำดับ ซึ่งประกอบด้วยจำนวนเต็มทั้งหมด $n$ ตัว จำนวนเต็มแต่ละตัวตั้งแต่ $1$ ถึง $n$ จะปรากฏเพียงหนึ่งครั้งเท่านั้นในลำดับทั้งหมดรวมกัน

เขาต้องการผสานลำดับเหล่านี้ให้เป็นเพอร์มิวเทชัน $p$ ที่มีความยาว $n$ ในตอนเริ่มต้น $p$ จะว่างเปล่า ในแต่ละขั้นตอน เขาจะเลือกลำดับที่ไม่ว่างหนึ่งลำดับ นำจำนวนเต็มตัวแรกของลำดับนั้นออก แล้วนำจำนวนเต็มนี้ไปต่อท้าย $p$ เขาจะทำเช่นนี้ซ้ำไปเรื่อยๆ จนกว่าลำดับทั้งหมดจะว่างเปล่า

จำนวนเต็มจะถูกเรียกว่าจุดตรึงของ $p$ หากค่าของมันเท่ากับตำแหน่งของมันใน $p$ โดยตำแหน่งจะถูกกำหนดหมายเลขตั้งแต่ $1$ ถึง $n$

จงหาจำนวนจุดตรึงที่เป็นไปได้น้อยที่สุดใน $p$

ข้อมูลนำเข้า

มีหลายกรณีทดสอบ บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็มเพียงตัวเดียว $T$ ($1 \le T \le 10^6$) ซึ่งระบุจำนวนกรณีทดสอบ

สำหรับแต่ละกรณีทดสอบ บรรทัดแรกประกอบด้วยจำนวนเต็มสองตัวคือ $n$ และ $m$ ($1 \le m \le n \le 10^6$) ซึ่งระบุจำนวนทั้งหมดของจำนวนเต็มและจำนวนของลำดับ ตามลำดับ

อีก $m$ บรรทัดถัดไปอธิบายลำดับต่างๆ บรรทัดที่ $i$ ของบรรทัดเหล่านี้ประกอบด้วยจำนวนเต็ม $k_i$ ($1 \le k_i \le n$) ตามด้วยจำนวนเต็ม $k_i$ ตัวคือ $a_{i,1}, a_{i,2}, \ldots, a_{i,k_i}$ ($1 \le a_{i,j} \le n$) ซึ่งอธิบายลำดับที่ $i$ ตามลำดับ

รับประกันว่าผลรวมของ $k_i$ จากทุกลำดับในแต่ละกรณีทดสอบมีค่าเท่ากับ $n$ และจำนวนเต็มแต่ละตัวตั้งแต่ $1$ ถึง $n$ จะปรากฏเพียงหนึ่งครั้งเท่านั้นในลำดับทั้งหมดรวมกัน

รับประกันว่าผลรวมของ $n$ จากทุกกรณีทดสอบไม่เกิน $10^6$ และผลรวมของ $m$ จากทุกกรณีทดสอบไม่เกิน $10^6$

ข้อมูลส่งออก

สำหรับแต่ละกรณีทดสอบ ให้แสดงผลหนึ่งบรรทัดซึ่งประกอบด้วยจำนวนเต็มเพียงตัวเดียว ที่ระบุจำนวนจุดตรึงที่เป็นไปได้น้อยที่สุดใน $p$

ตัวอย่าง

ข้อมูลนำเข้า 1

4
1 1
1 1
3 2
1 1
2 2 3
3 2
2 1 3
1 2
4 2
3 2 1 3
1 4

ข้อมูลส่งออก 1

1
0
1
0

หมายเหตุ

ในกรณีทดสอบตัวอย่างที่หนึ่ง เพอร์มิวเทชันเดียวที่เป็นไปได้คือ $[1]$ ซึ่งมีจุดตรึงหนึ่งจุด

ในกรณีทดสอบตัวอย่างที่สอง Little Cyan Fish สามารถสร้าง $p = [2, 3, 1]$ ซึ่งไม่มีจุดตรึงเลย

ในกรณีทดสอบตัวอย่างที่สาม $p = [1, 3, 2]$ เป็นเพอร์มิวเทชันที่เหมาะสมที่สุดซึ่งมีจุดตรึงหนึ่งจุด

ในกรณีทดสอบตัวอย่างที่สี่ เขาสามารถสร้าง $p = [2, 4, 1, 3]$ ซึ่งไม่มีจุดตรึงเลย