暂无测试数据。

Background

很多机会转瞬即逝，错过了就是错过了。

Description

公元 3926 年，人类发明出了时光机。 得知这个消息的小 A，不禁回想起自己人生中也错过了许多机会，有很多的错过让小 A 至今感到后悔。
小 A 决定乘坐时光机改变过去。 时光机的操作页面上有 n 个排成一列的按钮，还有 n 个排成一圈的按钮（即第 1 个按钮与第 n 个按钮 相邻），启动时光机需要同时满足以下 2 个条件：
1. 在 n 个排成一列的按钮中至少按下两个按钮，且被按下按钮中任意相邻按钮间相距的按钮数量相同。
2. 在 n 个排成一圈的按钮中至少按下两个按钮，且被按下按钮中任意相邻按钮间相距的按钮数量相同。 当 n = 4 时，所有的排成一列和排成一圈的合法方案如下图（红色表示按钮被按下，蓝色表示按钮未被按下）：
（懒得贴图）
小 A 想知道他有多少种方案能够启动时光机，请你帮他求出这个值。 由于小 A 有很多事情需要改变，所以需要多次启动时光机，因此有多组数据。

Format

Input

从 count.in 读入输入数据。
第一行一个整数 T，表示数据组数。
接下来 T 行每行一个整数 n。

Output

将答案输出到 count.out 中。
对于每组数据需要求出 3 个数，分别为：能够启动时光机的方案数 A，满足第 1 个条件的方案数 B ，满足第 2 个条件的方案数 C。由于答案可能很大，只需要求出它们对 999392699 取模的结果。
由于输出量会很大，所以只需要输出 3 个数，代表所有 A、所有 B、所有 C 分别的异或和。

Sample 1

Input

1
4

Output

27 9 3

【样例解释】

需要注意的是，「只满足第 x 个条件」时不需要考虑其他 n 个按钮，这也是后两个输出是 9, 3 的原因。

Limitation

1s, 1024KiB for each test case.

Hint

本题读入量很大，请使用较快的读入方式。

对于 100% 的数据，1 ≤ T, n ≤ \(10^7\)。

Afterword

即使回到过去也无法改变。

Source

2021-9-20 contest