Problem Description

星光数问题

问题描述

在遥远的未来，人类发现了一种特殊的能量源——星光数，它是指那些完全平方数。为了有效利用这些能量，科学家们需要筛选出能被 3 整除的星光数。

现在有 ( T ) 组调查任务，每组给定一个范围上限 ( n )，你需要找出在 ( 1 ) 到 ( n ) 的所有星光数中，有多少个能被 3 整除。

输入格式

每个测试点包含多组调查数据。

第一行输入一个正整数 ( T )，表示调查任务的数量。

接下来的 ( T ) 行，每行输入一个正整数 ( n )，表示每组调查的范围上限。

输出格式

对于每组调查，输出一行一个整数，表示符合条件的星光数的个数。

输入输出样例

输入样例

3
9
50
100

输出样例

1
2
3

样例解释

共有三组调查任务：

• 第一组，符合条件的星光数为 ( 9 )；
• 第二组，符合条件的星光数为 ( 9, 36 )；
• 第三组，符合条件的星光数为 ( 9, 36, 81 )。

数据范围与约定

本题采用捆绑测试。

对于全部数据，满足 ( 1 < T < 10^5 )，( 1 < n < 10^18 )。