package competitive;
import java.math.BigInteger;
import java.util.Scanner;
public class Fibosum {
static int mod = 10000000;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
long m = sc.nextLong();
long n = sc.nextLong();
long ans1 = fab(m + 1)-1;
long ans2 = fab(n + 2)-1;
// System.out.println(ans1);
System.out.println((ans2 - ans1) % mod);
}
}
public static long fab(long n) {
if (n == 0) {
return 0;
}
long t[][] = new long[2][2];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
if (i < 1) {
if (j == i + 1) {
t[i][j] = 1;
} else {
continue;
}
}
t[i][j] = 1;
}
}
t = power(t, n - 1);
long f1[] = { 1, 1 };
// BigInteger ans = new BigInteger("0");
long ans = 0;
for (int i = 0; i < 2; i++) {
// long k = (t[0][i] * f1[i]) % mod;
ans = (ans + ((t[0][i] * f1[i]) % mod)) % mod;
}
return ans;
}
public static long[][] power(long arr[][], long b) {
if (b == 1 || b == 0) {
return arr;
}
if ((b & 1) != 0) {
return mutiply(arr, power(arr, b - 1));
} else {
long s[][] = power(arr, b / 2);
return mutiply(s, s);
}
}
public static long[][] mutiply(long[][] t, long[][] power) {
// TODO Auto-generated method stub
long ans[][] = new long[t.length][t.length];
for (int i = 0; i < t.length; i++) {
for (int j = 0; j < t.length; j++) {
for (int x = 0; x < t.length; x++) {
ans[i][j] = ((ans[i][j] + ((t[i][x] * power[x][j]) % mod)) % mod);
}
}
}
return ans;
}
}