大预言家！！！！

题号：NC289444
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 取完魔泉，你背着Askalana准备离开这座遗迹，但来时的路已经被封死，你们只能另辟蹊径。
$\hspace{15pt}$ 你们来到了一座大门前，门的最中心有一只紫色甲虫，啃着那一块金光闪闪的胶状物体。你们发现门边有一匾，上书：看破迷雾，破除污秽，即可畅行无阻。
$\hspace{15pt}$ 牌匾的背后有一图腾，描绘了这种”污秽甲虫“的行为模式，你认为它表示甲虫会绕中心以螺旋状行进。
$\hspace{15pt}$ 正当你们思考的时候，眼前的门扉被凭空出现的迷雾遮挡，窸窸窣窣的声音隐隐传来。

$\hspace{15pt}$ 我们在门扉的平面上建立以上、右为正方向的平面直角坐标系，甲虫初始第 $1$ 秒在 $(0,0)$ 的位置，每秒会先在当前所在格播撒污秽，之后按以下规则移动 $1$ 个单位长度：
$\hspace{23pt}\bullet\,$ 初始速度方向为右（即速度向量 $\vec{v_1} = (1, 0)$ ）；
$\hspace{23pt}\bullet\,$ 每秒移动前检查当前行进方向的右侧格子，如果这个格子没有污秽，则立即右转 $90$ 度；否则，继续沿原方向行进。

$\hspace{15pt}$ 在这里，记 $t$ 时刻的坐标为 $(x_t,y_t)$ ，速度向量为 $\vec{v_t} = (v_{x_t}, v_{y_t})$ ，那么当前行进方向的右侧格子的坐标为： $(x_t + v_{y_t},\ y_t - v_{x_t})$
$\hspace{15pt}$ 如果执行右转操作，那么右转后得到的新速度向量为： $\overrightarrow{v_{t+1}} = \begin{pmatrix} v_{y_t} \\ -v_{x_t} \end{pmatrix} = (v_{y_t}, -v_{x_t})$

$\hspace{15pt}$ 如图所示，甲虫最终会呈顺时针螺旋状绕原点移动：

$\hspace{15pt}$ 你需要隔着迷雾攻击甲虫，所以你需要确定第 $t$ 秒时甲虫的位置 $(x_t, y_t)$ ，来给猫猫指示一个准确的攻击坐标。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
在一行上输入一个正整数  代表询问的秒数。

除此之外，保证单个测试文件中，每一组测试数据询问的时间依次增大。即对于第  组测试数据，记  为询问的时间，则满足 。

输出描述:

对于每一组测试数据，新起一行。输出两个整数 ，代表第  秒时甲虫的位置为 。

示例1

输入

复制

输出

复制