题目描述

一轮不喜欢火车的上铺，于是坐在硬座上刷起了手机。突然，他刷到一道有意思的数学题：

• 如果有两个正整数 $a$ 和 $b$ ，使得:

为整数，那么这个整数一定是个完全平方数。

一轮来了兴趣，他想知道：当 $a$ 和 $b$ 都在 $[1,n]$ 范围内时，有多少个有序正整数对 $(a,b)$ 满足这个条件？

输入格式

每个测试文件包含多组测试数据。

第一行包含测试数据的组数 $T$ ($1≤T≤10^6$）。

每组测试数据的第一行包含一个整数 $n$ ($1≤n≤10^6$)，表示满足条件的数对数量。

输出格式

对于每组数据，输出一行一个整数，表示在 $[1,n]$ 范围内时，有多少个有序正整数对 $(a,b)$ 满足这个条件。

2
1
8

1
3

解释

• 第一个样例是 $(1,1)$ $1$ 个。

• 第二个样例是 $(1,1)$，$(2,8)$，$(8,2)$ $3$ 个。