题目描述

在第一象限中，一个格点$(x, y)$（$x$和$y$为大于等于$0$的整数），如果从原点$(0, 0)$到$(x, y)$的直线不经过任何其他格点，则该点被称为可见的。例如，点$(4, 2)$不可见，因为从原点出发的直线会经过$(2, 1)$。下图展示了$0 \leq x, y \leq 5$范围内所有可见点及其从原点出发的连线。

编写一个程序，给定尺寸$N$，计算满足$0 \leq x, y \leq N$的可见点的数量。

输入格式

第一行包含一个整数$C$（$1 \leq C \leq 1000$），表示数据集的数量。

接下来的$C$行，每行包含一个整数$N$（$1 \leq N \leq 1000$），表示网格的尺寸。

输出格式

对于每个数据集，输出一行，包含数据集编号（从$1$开始）$N$的值以及可见点的数量，格式为：数据集编号$N$可见点数量。

样例输入

4
2
4
5
231

样例输出

1 2 5
2 4 13
3 5 21
4 231 32549

来源

2006年大纽约地区编程竞赛