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