Guessing Game 是 Alice 最喜欢的双人游戏。这个游戏使用一副牌，每张牌上都写有一个由 0 和 1 组成的序列。所有牌上序列的长度都相等。

在 Guessing Game 中，Alice 从牌堆中随机抽取一张牌，另一名玩家试图通过询问 Alice 一系列形如“序列的第 $i$ 位数字是什么？”的问题来确定牌上的序列。在每次提问后，Alice 会（如实）回答该问题，之后第二名玩家可以继续提问，或者尝试猜测牌上的序列。第二名玩家只有一次猜测机会，如果猜测正确则获胜，否则失败。

Alice 向你发起挑战，要求你以尽可能少的提问次数赢得游戏。

CHALLENGE ACCEPTED

给定所有牌上的序列，求出无论 Alice 抽取哪张牌，为了唯一确定该序列所需的最少提问次数。

输入格式

第一行包含测试用例的数量 $z$ ($1 \le z \le 20$)。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n, k$ ($1 \le n \le 2^k; 1 \le k \le 13$)，分别表示牌的数量和所有序列的长度。接下来的 $n$ 行，每行包含一个长度为 $k$ 的由 0 和 1 组成的字符串，描述一张牌上的序列。同一测试用例中没有两个序列是相同的。

输出格式

对于每个测试用例，输出一个整数：第二名玩家为了赢得游戏所需询问的最少问题数量。

样例

输入格式 1

1
4 3
000
100
010
011

输出格式 1

2