题目描述

给定一个正整数 $n$。

定义“好数”是满足以下条件的正整数：

• 可以表示为 $x^4+3x+1$ 的形式，其中 $x$ 是非负整数。

定义“坏数”是满足以下条件的正整数：

• 可以表示为 $x^4+4x+1$ 的形式，其中 $x$ 是非负整数。

你有一个数 $a$，初始为 $0$。你可以对 $a$ 进行任意多次操作，每次可以进行以下两种操作之一：

• 选择一个“好数”$k$，将 $a$ 变为 $a+k$。
• 选择一个“坏数”$k$，将 $a$ 变为 $a-k$。

你需要保证每次操作后 $0\le a\le 2n$。请你用最小的操作次数使 $a$ 变为 $n$。

输入格式

本题有多组测试数据，第一行一个正整数 $T$ 表示测试数据组数。

接下来 $T$ 行，每行一个正整数 $n$。

输出格式

对于每组测试数据，输出一个正整数 $m$ 表示最小的操作次数。

2
641
1042

1
2

提示

样例解释

对于 $n=641$，你可以进行 $1$ 次操作使 $a$ 变为 $641$：

• 选定“好数”$641$（可以表示为 $5^4+3\times5+1$ 的格式），将 $a$ 增加 $641$。

对于 $n=1042$，你可以进行 $2$ 次操作使 $a$ 变为 $1042$：

• 选定“好数”$1315$（可以表示为 $6^4+3\times6+1$ 的格式），将 $a$ 增加 $1315$。
• 选定“坏数”$273$（可以表示为 $4^4+4\times4+1$ 的格式），将 $a$ 减少 $273$。

数据范围

对于 $100\%$ 的数据，$1\le T\le 5$，$1 \le n \le {10}^6$。