Description

隔离罩是用来尽量防止其他宇宙射线对于扫描仪（不是牵引器！）的损坏的重要部件。

简单的，我们可以把切割前的隔离罩看成一个单位球面如下图所示：

工作计划上要完成 $N$（$1 \le N \le {10}^6$）次观测任务。

对于第 $i$ 观测次，我们从点 $(0,0)$ 出发，扫描位于点 $(x_i,y_i,z_i)$，半径为 $r_i$（$-{10}^6 < x_i,y_i < {10}^6$，$0 < r_i < z_i < {10}^6$）的陨石。
这里我们可以简单的将陨石认为成一个圆球体。

每次观测我们都要保证我们可以通过防护罩上开的洞扫描陨石的全貌。

现在请你计算我们将要开的防护罩上的圆洞在球面上的半径（大圆弧长），即所有陨石球在上半单位球投影的并的最小覆盖圆（这里的圆是在曲面上的）。

由于是单位球，所以这个数值应该等于该圆洞直径上两点与球心连线所呈平面角角度的一半。

显然的，这个角度小于 $\frac{\pi}{2}$ 大于 $0$。若角度为 $\omega$ rad 请你输出 $\frac{\omega}{\pi/2} \times {10}^5$ 并向下取整。

Input Format

第一行一个整数 $N$，代表后面有 $N$ 个观测计划。

之后每行四个整数，以空格分割，依序分别为 $x_i,y_i,z_i,r_i$。

Output Format

输出一个范围在 $[0, 99999]$ 的整数。

5
30 10 10 9
100 -10 100 50
-30 100 50 30
12 42 64 20
287 123 46 31

67877

Hint

【样例解释】

下图是各个小行星投影至防护罩的圆和最后挖出来圆洞的示意图。

【提示】

• 这并不是一道计算机图形学题目。
• 背景故事中所有人物、时间、事件、文字均为虚构。
• 输入较大，建议使用更好的读入输出方式。
• 请尽可能地利用您的代数知识。

【题目来源】

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）。

题解等资源可在 https://github.com/yylidiw/thupc_2/tree/master 查看。