Cho số nguyên dương ~S~. Hãy đếm số dãy số nguyên dương (có thứ tự) có tổng các phần tử bằng ~S~ và ước chung lớn nhất của tất cả các phần tử bằng ~1~.

Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho ~10^9 + 7~.

Input

• Dòng đầu tiên chứa số nguyên ~T~, số bộ test.
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~S~.

Output

Với mỗi bộ test, in ra trên một dòng số dãy thỏa mãn, lấy dư cho ~10^9 + 7~.

Ví dụ

Input

1
4

Output

6

Giải thích: có ~2^3 = 8~ dãy có tổng bằng ~4~. Loại bỏ hai dãy ~(4)~ và ~(2, 2)~ có ước chung lớn nhất khác ~1~, còn lại ~6~ dãy.

Giới hạn

• ~1 \le S \le 10^9~

Vào/ra bằng file

• Dữ liệu vào: đọc từ file DEMDAY.INP.
• Kết quả: ghi ra file DEMDAY.OUT.