题目描述

在遥远的西方，古法兰克地区有一片黄沙障壁的荒芜之地，沙尘深处衍生出了一片远离尘嚣的村落，这是这片荒芜之地唯一的文明，由于长期无人问津，这片村落赓续着许多古老而奇异的传统。 在村落的正中央矗立着一株繁茂的石榴树，这也许是这片荒地唯一的生机，村民们在树前搭建了 $N$ 个祭坛，每年村民都会将树上掉落的石榴摆布在祭坛上，为了表示长久而崇高的敬仰，这 $N$ 个祭坛上摆布的石榴 $a_1$ ~ $a_N$ 恰好是 $1$ ~ $N$ 的一个排列，同时为了避讳，村民对祭坛上的石榴数作出如下约束：

• 对于每个祭坛石榴数 $a_i$ 需满足 $a_i≠i$。

摆放石榴的方式有很多种，而每种方式为村落带来的神祈值 $S$ 可能会有所不同，其中 $S$ 的计算方式如下：

• $S=|a_1-1| + |a_2-2| + |a_3-3| + ... + |a_n-n|$。

也就是每个祭坛石榴数与祭坛编号的差值之和。 但村民并不能清楚地算出神祈值 $S$，这天聪明的探险家 @zls_XICK 意外发现了这个遗失村落，于是他想要帮助村民计算最佳的神祈值 $S$，并试着帮助村民摆放石榴。

村民认为神祈值 $S$ 最小时，获得的祝福最大，但他们也不希望神祈值 $S$ 变为 $0$，若不存在合规的摆放方案，神祈值 $S$ 会变为 $0$。

于是他想要计算 $N$ 个祭坛可以得到的最小神祈值 $S_{min}$ 是多少，并求出可以使神祈值 $S$ 最小的石榴摆放方案数 $K$。

特此鸣谢 @Lelzy 对数据点配置错误指出。

输入格式

本题包含多组测试数据

第一行输入一个整数 $T$ 表示数据总数。

后对于每组数据输入一行一个整数 $N$ 表示祭坛数。

输出格式

对于每组输入输出一行两个整数。

分别表示最小神祈值 $S_{min}$ 以及满足神祈值最小的方案数 $K$。

两个整数用空格隔开。

2
2
3

2 1
4 2

数据规模与约定

对于 $20\%$ 的数据保证 $1 \le N \le 8$, $1 \le T \le 5$。

对于另外 $20\%$ 的数据保证 $1 \le N \le 5\times 10^6$。

对于 $100\%$ 的数据保证 $1 \le T \le 10$, $1 \le N \le 3\times 10^9$。