Döşəmənin rənglənməsi

Müze Bizarre Argentinean Pocket Calculators (BAPC) muzeyi, döşəməyə gözəl bir rəsm çəkmək üçün istedadlı bir rəssam tapıb. Muzeyin bütün divarları düzdür və hər iki qonşu divar bir-birinə dik bucaq altında kəsişir. Qeyri-qonşu divarlar isə bir-biri ilə kəsişmir. Bundan əlavə, rəsmin yerləşdiriləcəyi otaqda sütunlar yoxdur. Beləliklə, otaq düz xəttli sadə çoxbucaqlıdır.

Rəsmin dizaynı kvadrat şəklindədir. Muzey, rəsmin mümkün qədər böyük olmasını istəyir. Bundan əlavə, kvadratın kənarları divarlara paralel olmalıdır. Rəsmin maksimal mümkün enini tapın.

Giriş məlumatları

Birinci sətir testlərin sayını göstərir, maksimum 100. Daha sonra hər bir test üçün:

• birinci sətir n (4 ≤ n ≤ 1 000) ədədini ehtiva edir - otağın künclərinin sayı.

• n sətir, hər biri iki tam ədəd x və y (0 ≤ x, y ≤ 100 000) ehtiva edir: otağın hər bir küncünün koordinatları.

Künclər saat əqrəbi istiqamətində verilir.

Çıxış məlumatları

Hər bir test üçün ayrıca sətirdə muzeyin döşəməsinə yerləşdirilə bilən kvadrat rəsmin maksimal enini çıxarın.