U412490 数数

**时间限制：** 1.0 秒 **空间限制：** 512 MB 注：本题数据的输入输出格式与原题进行了微调，将一组输入改成多组输入。我们有 10 个计入分数的测试点（每个测试点 10 分）以及 10 个不计入分数的测试点（每个测试点 0 分），只通过前 10 个测试点视为 100 分 `unaccepted` ，通过所有测试点视为 `accepted` 。

对于每个数据点你需要处理 $T$ 组查询。每次查询输入 $n$ ，求长度为 $n$ 的字符串个数，要求： - 每一位为 `1` , `2` 或 `3` ; - 不得连续出现 3 个相同的数字。

无

无

### 样例解释 对于 $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`。 ### 数据范围 本题分两个 subtask ，每个 subtask 内部采用传统计分方式。 subtask 1 : 每个测试点 10 分，所有数据保证 $T=1$ 。对于其中 $40\%$ 的数据，保证答案不超过 16 位数。对于 $100\%$ 的数据，保证 $n\le 10^6$ 。 subtask 2 : 每个测试点 0 分，所有数据保证 $T=10^5, n\le 10^6$ 。