Cho một hình chữ nhật kích thước ~2 \times N~. Hãy đếm số cách lát các viên gạch nhỏ kích thước ~1 \times 2~ và ~2 \times 1~ vào hình trên sao cho không có phần nào của các viên gạch nhỏ thừa ra ngoài, cũng không có vùng diện tích nào của hình chữ nhật không được lát.

Dữ liệu

-Gồm nhiều test, dòng đầu ghi số lượng test ~T~ ~(T ≤ 10^6)~. -T dòng sau mỗi dòng ghi một số ~N~ ~(1 ≤ N ≤ 10^6)~.

Kết quả

• Gồm ~T~ là ~T~ kết quả cần tìm chia dư cho ~10^9 + 7~.

Ví dụ

Dữ liệu 1

3
1
2
3

Kết quả 1

1
2
3

Bình và An chơi trò chơi ghép các cặp số nguyên tố đề tìm mối liên kết giữa chúng. Các bạn ấy muốn tìm ra những cặp số đặc biệt để ghép lại với nhau. Anh trai của An là một nhà Toán học, anh ấy cho hai bạn một số nguyên dương k và yêu cầu hai bạn tìm ra các cặp số nguyên tố tố anh em. Hai số nguyên tố a và b được goi là anh em nếu ~a – b = k~. Giả sử: ~k = 2~ ta có các cặp số anh em: ~(3, 5), (5, 7), (11, 13), (17,19),…~

Yêu cầu:

Cho hai số nguyên dương ~n~ và ~k~. Hãy đếm số lượng cặp số anh em trong phạm vi từ ~1~ đến ~n~.

Dữ liệu

• Gồm 1 dòng chứa hai số nguyên dương ~n~và ~k~ ~(1≤k≤n≤10^6)~.

Kết quả

• Một số nguyên là số lượng cặp số anh em tìm được.

Ví dụ

Dữ liệu 1

20 6

Kết quả 1

4

Ràng buộc

• Có 30% test tương ứng 30% số điểm thỏa mãn ~1<n≤10^2~</li>
• Có 70% test tương ứng 70% số điểm thỏa mãn ~10^2<n≤10^6~</li>