Như chúng ta đã biết, Rubik là một khối lập phương gồm có \(6\) mặt: trắng, u: khối \(2 * 2 * 2\), khối \(3 * 3 * 3\), khối \(4 * 4 * 4\), khối \(5\) *đỏ, vàng, cam, xanh lá, xanh dương. Có rất nhiều loại rubik khác nha \(5 * 5,...;\) ngoài ra còn có các dạng rubik biến thể khác.

Mấy bữa nay Tí đang tìm hiểu về rubik, Tí muốn biết khối rubik \(n^3\) được tạo thành từ bao nhiêu khối nhỏ hơn(khối ở tâm, khối ở cạnh, khối ở góc). Ví dụ: khối \(2 * 2 * 2\) có \(8\) khối nhỏ hơn ghép lại.

Input

• Dòng thứ nhất chứa số \(T(1 \leq T \leq 100000)\) - Thể hiện số lượng test case.
• \(T\) dòng tiếp theo, mỗi dòng chứa số nguyên \(n. (2 \leq n \leq 10 ^ {18})\).

Output

• Ứng với mỗi testcase, in ra số khối cần tìm khi chia lấy dư cho \(1000000007\).

Example

2
2
3

8
26