Cho \(3\) số nguyên \(1\), \(3\), \(5\) và một số nguyên dương \(N\), xác định xem có bao nhiêu chuỗi khác nhau được tạo ra từ \(3\) số nguyên đã cho mà tổng các ký tự của chuỗi bằng \(N\).

Input

• Dòng đầu tiên là số bộ test \(t\).
• \(t\) dòng tiếp theo, mỗi dòng là một số \(N\).

Output

• Với mỗi bộ test, output số lượng chuỗi khác nhau được tạo ra thỏa yêu cầu của đề bài.

Constraints

• \(1 \le t,N \le 150\)

Example

Sample input

2
6
10

Sample output

8
47