U140724 星际迷航

儒略历 998244353 天，灭霸颓然老矣，各路英雄都想要抢人头。于是，他们驾驶宇宙飞船在星际迷航，寻找灭霸的踪影。

在 DM 宇宙空间，共有 $n$ 颗星球，灭霸就在这 $n$ 颗星球当中，但谁也无法确定它究竟在哪颗星球上。每颗星球均有一个编码 $(x_i,y_i,z_i)$ 表示其在宇宙空间中的坐标。英雄们只能驾驶宇宙飞船来往于星球间。但他们并不是什么驾驶好手，只会直线飞行，甚至一脚油门下去就直接飞出去了好远。因此，这样的愣头青极有可能直接撞上星球，造成大量非战斗性减员。 不过幸好飞船还是会老化的。一开始（第 $0$ 天），飞船一脚油门能飞出去 $s$ 公里远。第 $i$ 天一脚油门会飞出去 $s-i$ 公里远。例如 $s=10$, 那么第一天就是 $9$ 公里，第二天 $8$ 公里，以此类推。 请问，到第几天时，英雄们 **一定能** 找到灭霸？每天可以踩任意脚油门，默认**只要第一脚油门下去不会撞机即可安全到达**。 当然，作为灭霸，也不能坐以待毙。因此，它将 $n$ 颗星球设置了通道，并天真的认为英雄只能从这些通道到达。所有通道都是双向的。一颗星球的发展程度为以这个星球为一端的道路数（无需考虑共线）。假设英雄们会先搜查发展程度为 $0$ 的星球，接下来搜查发展程度为 $1$ 的星球，以此类推直到发展程度为 $n-1$ 的星球。 注意所有星球的发展程度都是动态统计的。英雄们每搜查一颗星球，便会将其爆炸，这意味着所有与之有通道直接相连的星球的发展程度均会减一。发展程度为某个数的星球被视为同时攻击。 这意味着某些星球可能会幸运的躲过搜查。假设灭霸足够聪明来设计通道布局，那么永远无法被搜查到的星球最多有几颗？ 选手请注意，题目描述的两问 **相互独立**，互不影响。如第一问的星球编号和 $s$ 不适用于第二问，第二问中的通道和星球爆炸不适用于第一问。

无

无

### 数据范围 对于 $100\%$ 的数据，$1\le T\le 10,1\le n\le 1000,1\le x,y,z,s\le 10^9+7$。