As we know , the Fibonacci numbers are defined as follows:

Given two numbers a and b , calculate .

Input

The input contains several test cases. Each test case consists of two non-negative integer numbers a and b (0 a b 1,000,000,000). Input is terminated by a = b = 0.

Output

For each test case, output S mod 10000, since S may be quite large.

Sample Input

1 1
3 5
10 1000
0 0
Sample Output
1
16
5733