Kompüter oyunu
Con və Brüs kompüterdə hərbi-strateji oyun oynayırlar. Oyun dünya xəritəsinin düz səthində keçirilir. Oyunun əvvəlində Brüs öz ordusu üçün yerləri seçir, daha sonra Con öz ordusu üçün strateji nöqtələri aşağıdakı qaydalara əsasən seçməlidir:
Hər bir strateji nöqtə şəbəkə nöqtəsi (x, y) olmalıdır (şəbəkə nöqtəsi tam koordinatlara malik nöqtədir) və bu nöqtələr |x| + |y| < N şərtini ödəməlidir;
Con istədiyi qədər strateji nöqtə seçə bilər;
Bütün strateji nöqtələr bir-birindən fərqli olmalıdır;
Hər bir strateji nöqtə boş olmalıdır (yəni Brüsün ordusu tərəfindən tutulmamış olmalıdır);
Hər bir fərqli strateji nöqtə cütlüyü əlaqəli olmalıdır (bu əlaqə digər strateji nöqtələr vasitəsilə də ola bilər).
İki şəbəkə nöqtəsi (x_1, y_1) və (x_2, y_2) əlaqəlidir, əgər |x_1 - x_2| + |y_1 - y_2| = 1 şərtini ödəyirsə. Əgər A, B və C strateji nöqtələrdirsə və A ilə B əlaqəlidirsə, B ilə C əlaqəlidirsə, onda A ilə C də əlaqəlidir.
Giriş verilənləri
Birinci sətir bir tam ədəd T - testlərin sayını göstərir. Hər bir test bir boşluqla ayrılmış iki tam ədəd N və M ehtiva edən sətirlə başlayır. Burada N birinci qaydada göstərilən ədəddir. M isə Brüsün ordusu tərəfindən artıq tutulmuş dünya xəritəsindəki tam nöqtələrin sayını göstərir. Növbəti M sətirin hər biri bir boşluqla ayrılmış iki tam ədəd Xk və Yk ehtiva edir. Hər bir nöqtə (Xk, Yk) Brüsün ordusu tərəfindən tutulmuşdur.
Çıxış verilənləri
Hər bir test üçün Conun öz ordusu üçün strateji nöqtələri seçmək yollarının sayını göstərən bir sətir çıxarın.
Məhdudiyyətlər
1 <= T <= 74,
1 <= N <= 7,
1 <= M <= 225,
-7 <= X_k, Y_k <= 7,
Bütün (X_k, Y_k) fərqli olacaq.