Trong lý thuyết số học, bên cạnh việc nghiên cứu từng số riêng lẻ, việc khảo sát cấu trúc của cả một dãy số cũng mang lại nhiều điều thú vị.

Đặc biệt, mối liên hệ giữa các phần tử thông qua ước chung lớn nhất phản ánh mức độ liên kết về mặt số học giữa chúng.

Một dãy số nguyên dương được gọi là liên kết nếu ước chung lớn nhất của toàn bộ dãy bằng 1.

Mức độ liên kết của một dãy chính là tổng các phần tử trong dãy.

Ví dụ, dãy [1, 1, 1, 1] là một dãy liên kết có mức độ liên kết bằng 4, vì:

• Ước chung lớn nhất của dãy là 1.
• Tổng các phần tử là 4.

Cho một số nguyên dương \(S\), hãy đếm có bao nhiêu dãy số nguyên dương có cùng mức độ liên kết là \(S\).

Hai dãy được xem là khác nhau nếu số lượng phần tử khác nhau hoặc tồn tại một vị trí mà hai dãy có giá trị khác nhau.

Yêu cầu

Với mỗi test, cho một số nguyên dương \(S\).
Hãy đếm số dãy số nguyên dương có tổng bằng \(S\) và có ước chung lớn nhất bằng \(1\).

Vì kết quả có thể rất lớn, hãy in ra số dư của kết quả khi chia cho \(10^9 + 7\).

Input

• Dòng đầu tiên chứa số nguyên dương \(t\) (\(1 \le t \le 100\)), là số lượng test.
• \(t\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(S\) (\(1 \le S \le 10^9\)).

Output

• In ra \(t\) dòng.
• Dòng thứ \(i\) là đáp án của test thứ \(i\), lấy dư theo modulo \(10^9 + 7\).

Example

3 
4 
5 
1

6 
15 
1

Scoring

• Subtask 1 (\(30\%\) số điểm): \(1 \le S \le 20\).
• Subtask 2 (\(30\%\) số điểm): \(1 \le S \le 10^6\).
• Subtask 3 (\(40\%\) số điểm): \(1 \le S \le 10^9\).