Sənin Yolların#5701
Kiçik və yaxşı planlaşdırılmış düzbucaqlı bir şəhərdə, Phuketdə yaşayırsınız. Şəhərin mərkəzi sahəsi H kilometr × W kilometr ölçüsündədir. Bu mərkəzi sahə HW vahid bloklara bölünmüşdür, hər biri 1×1 km^2 ölçüsündədir. Qərbdən Şərqə doğru H+1 sıra, Şimaldan Cənuba doğru isə W+1 prospekt mövcuddur. Mərkəzi sahə, aşağıda göstərildiyi kimi, müstəvi üzərində bir düzbucaqlı kimi görünür.
Şəkil 1. H = 3 və W = 6 olan bir şəhərin mərkəzi sahəsi.
Hər kəsişməni müstəvi üzərindəki koordinatına görə müəyyən edə bilərik. Məsələn, yuxarıdakı şəkildə sol-alt künc (0, 0) kəsişməsi, sağ-yuxarı künc isə (6, 3) kəsişməsidir.
Eviniz sol-alt küncdədir (yəni, (0, 0) kəsişməsi) və universitetə sağ-yuxarı küncdə (yəni, (W, H) kəsişməsi) getmək istəyirsiniz. Üstəlik, universitetə heç bir çətinlik çəkmədən getmək istəyirsiniz; buna görə də, yalnız Qərbdən-Şərqə və Cənubdan-Şimala doğru getmək istəyirsiniz. Bu şəkildə gedərək, yuxarıdakı nümunədə universitetə çatmaq üçün 84 yol var.
K gün universitetə getmək istəyirsiniz. Hər səhər şəhər, təmizlik işləri üçün küçə və prospektlərin bəzi hissələrini bağlayır. Bağlama elə edilir ki, bağlanmış hissələrdən başqa bağlanmış hissələrə yalnız Qərbdən-Şərqə və Cənubdan-Şimala gedən yollarla çatmaq mümkün deyil.
Hələ də eyni Qərbdən-Şərqə və Cənubdan-Şimala strategiyasından istifadə edərək universitetə getmək istəyirsiniz. Hər gün üçün yalnız Qərbdən-Şərqə və Cənubdan-Şimala gedərək universitetə neçə yolla çata biləcəyinizi öyrənmək istəyirsiniz. Çünki nəticə çox böyük ola bilər, biz yalnız nəticəni modulo 2552 istəyirik.
Birinci sətir test halların sayı olan T tam ədədini ehtiva edir (1 ≤ T ≤ 5). Hər test halı aşağıdakı formatdadır.
Hər test halının birinci sətri 3 tam ədəd ehtiva edir: W, H və K (1 ≤ W ≤ 1000, 1 ≤ H ≤ 1000, 1 ≤ K ≤ 10000). W və H mərkəzi sahənin ölçüsünü göstərir. K universitetə getmək istədiyiniz günlərin sayını göstərir.
Növbəti K sətir küçə və prospektlərin qırılmış hissələri haqqında məlumatı təsvir edir. Daha dəqiq desək, 1+i sətiri üçün, 1 ≤ i ≤ K, Q_i tam ədədi ilə başlayır (1 ≤ Q_i ≤ 100), bu, bağlanmış hissələrin sayını göstərir. Sonra Q_i dəst 4 tam ədəd ilə təsvir olunan bağlanmış hissələr gəlir. Hər hissə 4 tam ədəd ilə təsvir edilir, A, B, C və D (0 ≤ A ≤ C ≤ W, 0 ≤ B ≤ D ≤ H) bu, (A, B) və (C, D) kəsişmələrini birləşdirən hissənin bağlandığını bildirir. Bu hissənin küçə və ya prospektin etibarlı bir hissəsi olduğu təmin edilir, həmçinin C-A ≤ 1, və D-B ≤ 1, yəni hissə 1 km uzunluğundadır.
Hər test halı üçün, hər gün üçün, proqramınız universitetə modulo 2552 ilə neçə yolla gedə biləcəyinizi ayrı sətirdə çıxarmalıdır. yəni, hər test halı üçün çıxış K sətir olmalıdır.
Nümunə 1