Ngày xưa có một chàng trai có vô số các bạn gái. Các cô gái nghĩ rằng họ là người duy nhất trong trái tim chàng, tuy nhiên chàng chỉ lừa dối các nàng. Có ngôi nhà được xây trên một con đường, và mỗi bạn gái của chàng ở trong một ngôi nhà này.
Một ngày nọ, anh muốn thăm người bạn gái của mình, tuy nhiên anh nhận ra rằng mình không thể thăm hai ngôi nhà cạnh nhau được, việc này quá nguy hiểm. Anh muốn biết rằng, mình có bao nhiêu cách chọn để thăm được ngôi nhà khác nhau sao cho không có hai ngôi nhà nào cạnh nhau.
Dữ liệu vào:
Dòng đầu tiên là số nguyên dương thể hiện số test ;
Mỗi dòng trong số dong gồm hai số nguyên .
Dữ liệu ra:
Gồm dòng là kết quả của test trong dữ liệu vào (được in ra theo modulo ).
