Pile The Integer Game

クリスマス当日。 人の友だちを持つcardrate君は、とあるカードゲームを持ってきました。そのゲームの名前は BSG というらしいです。
今からcardrate君はこのゲームを 人で遊びます。その際、各プレイヤーに 枚ずつ、プレイヤー毎のどのカードにおいても異なる整数が一つ一つ書いてあるカードを配ります。厳密にいうと、プレイヤー には 枚目のカードに が書かれたものが配られます。ただし全ての に対して が成り立つような入力が与えられます。

このゲームには何人だけプレイヤーが回ってきたかを表す、ターン数というものがあり、 人だけプレイヤーが回ってきた後のゲームの状態をターン と呼びます。
最初のターン (ターン ) では、プレイヤー からゲームを始めます。次のターン (ターン ) ではプレイヤー 、その次のターン(ターン )ではプレイヤー 、...、ターン でプレイヤー となり、ターン ではプレイヤー ...と、繰り返しゲームを行います。言い換えると、ターン ではプレイヤー がゲームを行います。ただし は を で割ったあまりを表します。

また、カードを出す場所を場と呼ぶことにします。BSG の以下のルールはに従ってゲームをします。

• ターン の直前のプレイヤー、すなわちターン にゲームを行うプレイヤーと、ターン にゲームを行うプレイヤーが場に出したカードに書かれた整数をそれぞれ とする。各ターン毎に行うプレイヤーはゲームを続ける度に が成り立つようなカードを必ず場に出さなくてはならない。そのようなカードがない場合、このゲームはターン の時点で終了する

このゲームができるだけ長く続くように各プレイヤーがカードを場に出すとき、ターン数は最大でいくつとなりますか？すなわちこのゲームが最大で何回だけ続けることができるかを求めてください。

・
・
・全ての に対し

答えを出力せよ。

4 4
1 2 10 19
7 10 11 13
8 10 13 15
9 18 20 21

9

次のようにゲームを進めることで、最大で 回だけ続けることが可能です:

・( 周目) プレイヤー が を書かれたカードを場に出す
・プレイヤー が を書かれたカードを場に出す
・プレイヤー が を書かれたカードを場に出す
・プレイヤー が を書かれたカードを場に出す
・( 周目) プレイヤー が を書かれたカードを場に出す
・プレイヤー が を書かれたカードを場に出す
・プレイヤー が を書かれたカードを場に出す
・プレイヤー が を書かれたカードを場に出す
・( 週目) プレイヤー が を書かれたカードを場に出す

回目のゲームでプレイヤー は場に出せないので を出力します。