Xông đất ngày Tết

View as PDF
Submit solution
Points: 1.16 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
Trên trời rơi xuống
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Bò đi xông đất vào ngày Tết. Khu phố nơi Bò ở có ~m~ ngôi nhà, Bò muốn xông đất đúng ~n~ ngôi nhà. Tuy nhiên Bò lại muốn xông đất sao cho không có ~2~ ngôi nhà nào kề nhau. Hỏi: Có bao nhiêu cách để xông đất thỏa mãn?

Kết quả theo module ~100003~ ~(10^{5} + 3)~

Input

Dòng đầu là số nguyên ~T~ (số test, ~T \le 10^{5})~.

Mỗi dòng trong ~T~ dòng sau chứa ~2~ số nguyên ~m~ và ~n~ ~(1 \le m~, ~n \le 10^{16})~

Output

Gồm ~T~ dòng, mỗi dòng là số cách tương ứng với từng test.

Sample Input

2
5 2
5 3

Sample Output

6
1

Comments

Please read the guidelines before commenting.