Cho một số nguyên dương S, xét tập tất cả các dãy số nguyên dương có tổng bằng S, hỏi trong tập này có bao nhiêu dãy mà ước số chung lớn nhất của tất cả các phần tử trong dãy bằng 1.

Ví dụ với S=4, ta có 6 dãy:

(1,1,1,1)

(1,1,2)

(1,2,1)

(2,1,1)

(1,3)

(3,1)

Dữ liệu:

• Dòng 1 chứa số nguyên dương ~t≤100~ là số test
• t dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~s≤10^9~ ứng với một test

Kết quả: Ứng với mỗi test, ghi ra một số nguyên duy nhất trên một dòng là số dư của kết quả tìm được khi chia cho ~10^9+7~

Ví dụ

INPut

2
1
4

output

1
6

Bộ test chia làm 3 subtasks:

• Subtask 1 (30% số điểm): ~S≤20~
• Subtask 2 (30% số điểm): ~S≤10^6~
• Subtask 3 (40% số điểm): Không có ràng buộc bổ sung