No submission language available for this problem.

Background

Special for beginners, ^_^

Description

对于一个整数 $n$，我们规定对于字符串 "ABC" 重复拼接 $n$ 次的串为 $s(n)$

比如 $s(1)$ = "ABC", $s(2)$ = "ABCABC"

由此也可以知道，一个 $s(n)$ 的串的串长为 $3n$

针对 $s(n)$, 你可以进行几次下面的一组操作（也可以是 $0$ 次）

• 选择串中的两个位置 $i$ 和 $j$ ($1 <= i, j <= 3n, i ≠ j$)
• 接着交换 $s(n)_i$ 和 是 $s(n)_j$

你所需要做的，是令 "ABC" 在一个 $s(n)$ 中不出现，即令 "ABC" 不是 $s(n)$ 的子串。那么对于 $s(n)$ 的最少操作次数是几次？

Format

Input

一行一个整数 $T$ 表示有 $T$ 组测试，每组一个整数表示 $n$

Output

有 $T$ 行，分别表示每个 $n$ 所对应的最少操作数

Samples

1

1

2

1

样例 1 说明：

ABC -> 1次 -> BAC

Limitation

1s, 1024KiB for each test case.