Little Square 的学校正在组织年度足球赛。两位队长分别是 Little Square 和 Little Triangle。他们将从学校的 $N$ 个班级中挑选队员。选拔规则如下：

• Little Square 和 Little Triangle 轮流挑选队员，Little Square 先手。
• 每一轮只能从同一个班级中挑选学生。
• 每一轮至少挑选 1 名学生，至多挑选 $K$ 名学生。
• 每一轮挑选的学生人数必须不超过上一轮挑选的人数。
• 挑选最后一名（或多名）学生的队长获得“Fo(1)otball”奖。

队长们并不关心总共挑选了多少学生，且所有学生在足球技能上都是相同的。他们只关心“Fo(1)otball”奖。假设双方都采取最优策略，谁会获胜？

输入格式

每个测试文件包含多个测试用例，描述不同的场景。第一行包含 $T$，即测试用例的数量。接下来是各测试用例的描述。每个测试用例的第一行包含 $N$ 和 $K$。第二行包含 $N$ 个正整数，表示 Little Square 学校中各班级的人数。

输出格式

输出 $T$ 个测试用例的答案，每个答案占一行。如果 Little Square 在某个测试用例中获胜，输出 1；否则输出 0。

数据范围

• $T \le 100\,000$
• 设 $\sum N$ 为所有测试用例中 $N$ 的总和，则 $\sum N \le 100\,000$
• $K$, 任意班级人数 $\le 1\,000\,000\,000$

子任务

• 子任务 1（26 分）：$K = 1$
• 子任务 2（8 分）：$N \le 10$，$\sum N \le 100$，任意班级人数 $\le 3$
• 子任务 3（11 分）：$N \le 10$，任意班级人数 $\le 5$
• 子任务 4（8 分）：$N = 1$，$K$, 任意班级人数 $\le 100$
• 子任务 5（16 分）：$N = 1$
• 子任务 6（16 分）：$K = 2$
• 子任务 7（7 分）：$K$ 是 2 的幂
• 子任务 8（8 分）：无附加限制

样例

输入格式 1

3
3 1
3 1 1
5 2
2 1 1 1 1
1 2
3

输出格式 1

1
1
1

说明

在第一个测试中，总共有 5 名学生，且每一轮必须恰好挑选 1 名学生（因为 $K = 1$）。因此，选拔将持续恰好 5 轮，最后一名学生将在 Little Square 的回合被挑选，Little Square 获胜。

在第二个测试中，Little Square 可以先从第一个班级挑选两名学生。随后，在接下来的四轮中，每位队长各挑选一名学生（因为此时所有班级都只剩下一名学生），Little Square 获胜。

在第三个测试中，一种获胜策略是 Little Square 先挑选一名学生。