ל-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]$, שאין לה נקודות שבת.