原题为单组测试，我们增加一组多测的子任务。

时间限制： 1.0 秒

空间限制： 512 MB

题目描述

对于每个数据点你需要处理 $T$ 组查询。每次查询输入 $n$，求长度为 $n$ 的字符串个数，要求：

• 每一位为 1，2 或 3;
• 不得连续出现 3 个相同的数字。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $T$ ，表示共有 $T$ 组数据。

接下来 $T$ 行，每组数据占一行，分别包含一个正整数 $n$。

输出格式

输出到标准输出。

共输出 $T$ 行，第 $i$ 行对应第 $i$ 组询问所求的答案：

• 如果答案不超过 16 位数，则直接输出。
• 如果答案至少 17 位数，则先输出 ...... ，然后输出答案的最后 10 位。

3
4
28
51

66
1970947301376
......9614132224

样例 1 解释

对于 $n=4$ , 符合条件的串有：

1121, 1122, 1123, 1131, 1132, 1133, 1211, 1212, 1213, 1221, 1223, 1231, 1232, 1233, 1311, 1312, 1313, 1321, 1322, 1323, 1331, 1332, 2112, 2113, 2121, 2122, 2123, 2131, 2132, 2133, 2211, 2212, 2213, 2231, 2232, 2233, 2311, 2312, 2313, 2321, 2322, 2323, 2331, 2332, 3112, 3113, 3121, 3122, 3123, 3131, 3132, 3133, 3211, 3212, 3213, 3221, 3223, 3231, 3232, 3233, 3311, 3312, 3313, 3321, 3322, 3323。

子任务

• 子任务 1（97 分）：对于所有数据保证 $T=1$，前 $40\%$ 的数据保证答案不超过 16 位数，所有数据保证 $n\le 10^6$。
• 子任务 2（3 分）：对于所有数据保证 $T=10^5,n\le 10^6$。