Sáng hôm nay, \(Kaninho\) được cô giáo khen vì đã làm được một bài toán hóc búa và để chia sẻ niềm vui này cho nhiều người, cậu ấy quyết định đăng bài toán này lên đây để mọi người cùng thử sức. Bài toán có đề bài như sau:

• Kí hiệu \(u(n)\) là số nguyên nhỏ nhất có tổng các chữ số bằng \(n\).

• Kí hiệu \(g(k)=\sum\limits_{n=1}^{k}u(n)\).

Gọi \(f_i\) là phần tử thứ \(i\) của dãy fibonacci, trong đó: \(f_0=0,f_1=1\) và \(f_{i}=f_{i-2}+f_{i-1}\) với mọi \(i\ge 2\)

Yêu cầu: Tính \(z(q)=\sum\limits_{i=2}^{q}g(f_i)\) với số \(q\) nguyên dương cho trước. Vì đáp án có thể lớn, nên ta cần mod \(10^9+7\) trước khi in ra.

Input

• Dòng thứ nhất chứa số \(t(1\le t\le 50)\) - Thể hiện số lượng testcase của bài toán

• \(t\) dòng tiếp theo, mỗi dòng chứa số nguyên dương \(q(2\le q\le 90)\)

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm

Scoring

• Subtask \(1\) (\(37,5\%\) số điểm): \(2\le q\le 10\)

• Subtask \(2\) (\(62,5\%\) số điểm): Không có điều kiện gì

Example

2
2
3

1
4