Bằng cách xếp những khối lập phương lại với nhau, ta có thể tạo nên những kim tự tháp cho riêng mình.

Vậy cần bao nhiêu khối lập phương để tạo nên một tháp lá bài có độ cao \(n\).

Input

• Dòng đầu, chứa số nguyên dương \(T\) (\(T \le 10^6\)) - số lượng câu hỏi.
• \(T\) dòng sau, mỗi dòng chứa một số nguyên dương \(n\) (\(n \le 10^9\)).

Output

• Gồm \(T\) dòng, mỗi dòng chứa số lượng khối lập phương tối thiểu để tạo một tháp có chiều cao \(n\) tương ứng (lấy số dư khi chia cho \(10^9 + 7\)).

Example

3
1
2
3

1
10
35