小Aと小SはACMのチームメイトです。小Aは目が大きく視力も優れており、データから奇妙な規則性を見抜くことがよくあります。

ある日のトレーニングで、小Sは紙に円を描きました。小Aは一目見て、「これは正17角形じゃないか！」と言いました。彼はさらに多くの正多角形の画像を取り出し、小Sに観察させましたが、小Sには何のことかさっぱり分かりませんでした。そこで、あなたに鑑定を依頼することにしました。

具体的には、多角形の最大辺数 $n$ が与えられたとき、小Aは以下の手順で平面上の $N$ 個の点を生成しました。

• まず、中心となる点 $(x, y)$ を選択します。この点は $(0, 0)$ に固定される場合と、$[-1, 1] \times [-1, 1]$ の範囲から一様に選択される場合があります。
• $[\max(3, n-5), n]$ の範囲から整数 $k$ をランダムに選択します。
• $(x, y)$ を中心とし、半径を $1$ とする円を考えます。この円に内接する正 $k$ 角形を一つ、一様にランダムに選択します。
• これを $N$ 回繰り返します。毎回、正 $k$ 角形の境界上の点 $u$ を一様にランダムに選択し、$\hat u = u + \mathcal N$ をデータに加えます。ここで、$\mathcal N$ はランダムなノイズであり、その2次元座標はそれぞれ独立に、平均 $0$、標準偏差 $0.01$ のガウス分布に従います。
• 以上のすべてのランダムなプロセスは独立です。

あなたは、これら $N$ 個の点から、多角形の辺数 $k$ を復元する必要があります。

入力

標準入力からデータを読み込みます。

この問題には複数のテストケースが含まれます。 最初の行に正整数 $T$ が入力され、テストケースの数を示します。

各テストケースについて、最初の行に2つの正整数 $N, n$ が入力され、それぞれ点数と多角形の辺数の最大可能値を示します。続く $N$ 行には、それぞれ2つの浮動小数点数 $\hat u_x, \hat u_y$ が入力され、点 $\hat u$ の座標を示します。入力されるすべての浮動小数点数は、有効数字6桁で保持されています。

出力

標準出力に出力します。

各テストケースについて、多角形の辺数 $k$ を出力してください。

入出力例

詳細は配布ファイルを参照してください。

注記

以下は、サンプルの第 $2, 4, 5, 8$ ケースの可視化画像です。

小課題

すべてのテストケースにおいて、$T=200$、$N=1000$、$3 \le n \le 30$ です。

本問題には10個のテストケースがあり、各テストケースは10点です。テストケースのグループ化は行われません。

採点方法

各テストケースにおいて、誤った回答が最大で1つまでであれば満点を獲得できます。それ以外の場合は得点を得られません。

注記

以下の数学的定義が必要になる場合がありますが、これらを理解していなくても解法には影響しません。

平均 $\mu$、標準偏差 $\sigma$ のガウス分布 $\mathcal N(\mu, \sigma^2)$ に従う確率変数 $X$ の確率密度関数は以下の通りです。 $$f(x) = \frac{1}{\sqrt{2 \pi} \sigma} e^{-\frac{(x-\mu)^2}{2\sigma^2}}$$ 確率密度関数 $f(x)$ を持つ連続確率変数 $X$ と実数 $a < b$ に対して、確率変数 $X$ が生成する値が区間 $(a, b)$ に含まれる確率は以下の通りです。 $$\Pr(X \in (a,b)) = \int_a^b f(x) dx$$

以下の問題の性質が必要になる場合があります。

ガウス分布の特徴として、密度は平均から左右に指数関数的な速度で減少します。そのため、標準偏差が小さい場合、確率変数の値は高い確率で平均に近い値となります。例えば、本問題の状況において $\mu = 0, \sigma = 0.01$ の場合、生成される乱数の絶対値が $0.04$ を超える確率は約 $6 \times 10^{-4}$、 $0.05$ を超える確率は $6 \times 10^{-7}$ 以下、 $0.07$ を超える確率は $3 \times 10^{-12}$ 以下となります。