Orange的棋子移动

题目描述

YAO送给了Orange一套神秘的棋盘游戏，现在有一个 $n \times n$ 的方形棋盘，棋盘由 $n \times n$ 个 $1 \times 1$ 的正方形格子构成。在游戏开始时，场上仅有一个棋子，位于棋盘的 $(1,1)$ 位置，Orange每次可以消耗一步，将棋子移动到所在格子的上下左右的相邻格子中（但是不能越界）。他的目标是将棋子移动到棋盘上坐标为 $(n, n)$ 的格子中。

当然，棋盘还有一个神奇的规则，如果棋子此时位于棋盘的 $(x,y)$，你可以将棋盘移动到任何一个 $(x',y')$，当且仅当 $x,y,x',y'$ 满足 $gcd(x,y) = gcd(x',y') \neq 1$，这种操作并不消耗步数。

请问如果告诉你棋盘的大小，Orange最小要花费多少步才能完成目标？

输入格式

输入包含多组测试数据，第一行为一个整数 $T$，表示测试数据的数量。 对于每组测试数据，输入一个整数 $n$，表示棋盘大小。

数据范围

$1 \le T \le 10^5$ $1 \le n \le 10^9$

输出格式

输出共由 $T$ 行，表示每组测试用例的答案。

样例 #1

样例输入 #1

1
2

样例输出 #1

2