题目描述

小W拥有许多张无向图。

在 $n$ 个点 $m$ 条边的无向简单图（无自环、无重边）中：

• 最大可能边数为

• 边的密度为

密度 $\rho$ 的取值范围为 $[0, 1]$，越接近 $1$ 说明图越稠密，越接近 $0$ 说明图越稀疏。

本题中，我们采用经验阈值 $n\log_2 n$ 来判定稀疏与稠密：

• 若 $m \ge n\log_2 n$，则该图为稠密图，输出 1；
• 否则该图为稀疏图，输出 0。

现在给定 $T$ 张无向图，请你对每一张图求出它的最大可能边数、边的密度，并判断它是稠密图还是稀疏图。

输入格式

输入第一行一个整数 $T$。

接下来 $T$ 行，每行两个整数 $n, m$，表示一张图的顶点数与边数。

输出格式

对于每组数据，输出两行：

• 第一行：一个整数和一个实数，中间用一个空格隔开，依次为最大可能边数 $M$ 和边的密度 $\rho$，其中 $\rho$ 保留两位小数（四舍五入）；
• 第二行：一个数 0 或 1。1 表示该图为稠密图，0 表示该图为稀疏图。

输入输出样例 #1

输入 #1

5
20 156
74 1710
89 2597
13 14
78 2548

输出 #1

190 0.82
1
2701 0.63
1
3916 0.66
1
78 0.18
0
3003 0.85
1

输入输出样例 #2

输入 #2

5
869 232449
897 320229
545 140707
945 379912
902 358144

输出 #2

377146 0.62
1
401856 0.80
1
148240 0.95
1
446040 0.85
1
406351 0.88
1

说明

$n$ 最大可达 $10^9$，$n(n-1)$ 可达 $10^{18}$。

样例解释

以样例一第 $1$ 组数据（$n=20, m=156$）为例：

• 最大可能边数 $M = \dfrac{20 \times 19}{2} = 190$；
• 边的密度 $\rho = \dfrac{2 \times 156}{20 \times 19} = \dfrac{312}{380} \approx 0.8211$，保留两位小数为 $0.82$；
• 因为 $n\log_2 n = 20 \log_2 20 \approx 86.44 \le 156$，所以是稠密图，输出 1。

样例一第 $4$ 组数据（$n=13, m=14$）：$M = 78$，$\rho = \dfrac{28}{156} \approx 0.1795 \to 0.18$；而 $13\log_2 13 \approx 48.1 > 14$，所以是稀疏图，输出 0。

数据范围

• 对于 $30\%$ 的数据，$2 \le n \le 10^4$。
• 对于 $50\%$ 的数据，$2 \le n \le 10^6$。
• 对于 $100\%$ 的数据，$2 \le n \le 10^9$，$1 \le m \le \dfrac{n(n-1)}{2}$，$1 \le T \le 2 \times 10^5$。