有 $$$n$$$ 个岛屿,编号为 $$$1、2、\ldots、n$$$。最初,每对岛屿都通过一座桥梁连接起来。因此,总共有 $$$\frac{n (n - 1)}{2}$$$ 桥。
Everule 住在 $$$1$$$ 岛上,喜欢通过桥梁游览其他岛屿。统治者有能力摧毁最多$$$k$$$桥梁,以最大限度地减少Everule可以使用(可能是多个)桥梁到达的岛屿数量。
找出如果统治者以最佳方式摧毁桥梁,Everule 可以访问的最小岛屿数量(包括岛屿 $$$1$$$)。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行也是唯一一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 100$$$, $$$0 \le k \le \frac{n \cdot (n - 1)}{2}$$$)。
输出
对于每个测试用例,输出如果 Dominer 以最佳方式摧毁桥梁,Everule 可以访问的最小岛屿数量。
示例
输入 #1
6 2 0 2 1 4 1 5 10 5 3 4 4
输出 #1
2 1 4 1 5 1
注意
在第一个测试用例中,由于无法摧毁任何桥梁,因此所有岛屿都可以到达。
在第二个测试用例中,您可以摧毁 $$$1$$$ 岛和 $$$2$$$ 岛之间的桥梁。 Everule 将无法访问 $$$2$$$ 岛,但仍可以访问 $$$1$$$ 岛。因此,Everule 可以访问的岛屿总数为 $$$1$$$。
在第三个测试用例中,无论 Dominer 做什么,Everule 总是有办法到达所有岛屿。例如,如果统治者摧毁了$$$1$$$和$$$2$$$之间的桥梁,Everule仍然可以通过$$$1 \to 3 \to 2$$$访问$$$2$$$岛,因为$$$1$$$和$$$3$$$之间以及$$$3$$$和$$$2$$$之间的桥梁没有被摧毁。
在第四个测试用例中,您可以销毁自 $$$k = \frac{n \cdot (n - 1)}{2}$$$ 以来的所有桥梁。 Everule 将只能访问 $$$1$$$ 岛(island $$$1$$$)。