Q Calendar Square

この問題は KUPC2025 の中で \(2\) 番目に簡単であると想定されています。 Universal Cup への移植時は削除されます。

日曜始まり、土曜終わりのカレンダーを考えます。この問題では、暦の定義は グレゴリオ暦 に従います。

厳密には、 \(Y\) 年 \(M\) 月のカレンダーは次の方法で描かれます。

• まず、十分行数の大きい \(7\) 列のグリッドを用意する。はじめ、全てのマスは空白である。このグリッドの上の行から \(1,2,\dots\) 行目、左の列から \(1,2,\dots,7\) 列目と番号を付けることにする。
• 次に、 \(1\) 列目を日曜、 \(2\) 列目を月曜、 \(\dots\) 、 \(7\) 列目を土曜と定める。
• 次に、 \(Y\) 年 \(M\) 月 \(1\) 日の曜日を求め、 \(1\) 行目の対応する列に \(1\) を書く。
• その後、 \(Y\) 年 \(M\) 月 \(d\) 日を書くことを当月末日まで繰り返す。
  • もし \(d\) 日が日曜であれば、前日を書いた行のひとつ下の行の \(1\) 列目に \(d\) を書く。
  • そうでなければ、前日を書いたマスの \(1\) つ右のマスに \(d\) を書く。

画像は \(2026\) 年 \(3\) 月のカレンダーです。但し、曜日の表記は便宜上書き加えたものです。

\(Y\) 年 \(M\) 月のカレンダーについて、以下の構造を カレンダー正方形 と呼びます。

• \(u\) 行目から \(d\) 行目、 \(l\) 列目から \(r\) 列目までを取り出した時、全てのマスに数字が書かれている。
• ただし、 \(d-u=r-l\) でなければならない。
• このとき、この構造を 大きさ \(d-u+1\) のカレンダー正方形と呼びます。

例えば、

• \(14\) 日のみからなる構造は大きさ \(1\) のカレンダー正方形です。
• \(22,23,29,30\) 日からなる構造は大きさ \(2\) のカレンダー正方形です。
• \(3,4,5,6,10,11,12,13,17,18,19,20,24,25,26,27\) 日からなる構造は大きさ \(4\) のカレンダー正方形です。

\(Y\) 年 \(M\) 月に含まれるカレンダー正方形について、最大のものの大きさを求めてください。