Wheel

Într-un laborator se construiesc niște roți din sfoară și cuie.

Pentru un număr natural $n \geq 4$, roata de mărime $n$ se construiește astfel:

• se pun $n$ cuie pe conturul unui cerc, numerotate $1,2,\dots,n$ (în ordine);
• se pune un cui în centru, numerotat $0$;
• se leagă cu sfoară fiecare cui de pe cerc cu următorul, adică $(1,2), (2,3), \dots, (n-1,n), (n,1)$;
• se leagă cu sfoară centrul $0$ de fiecare cui de pe cerc: $(0,1), (0,2), \dots, (0,n)$.

Un tur închis este o succesiune de cuie distincte (în afară de primul și ultimul, care coincid) astfel încât între cuie consecutive există sfoară. Un tur închis este elementar dacă nu repetă niciun cui, în afară de faptul că se întoarce în punctul de plecare. Un tur elementar trebuie sa conțină cel puțin $3$ cuie distincte.

Pentru roata de marime 6 turul $1 \rightarrow 0 \rightarrow 3 \rightarrow 2 \rightarrow 1$ este un tur închis elementar. În desenul de mai sus, muchiile acestui tur sunt marcate cu roșu.

Notăm cu $C(n)$ numărul de tururi închise elementare din roata de mărime $n$.

Considerăm că două tururi închise elementare sunt același tur dacă unul se poate obține din celălalt prin:

• alegerea unui alt punct de start (rotație), și/sau
• parcurgerea în sens opus (inversare).

Altfel, tururile sunt distincte.

Turul $1 \rightarrow 0 \rightarrow 3 \rightarrow 2 \rightarrow 1$ este același cu $0 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 0$ (același tur, alt start) și cu $1 \rightarrow 2 \rightarrow 3 \rightarrow 0 \rightarrow 1$ (același tur, sens opus).

Cerință

Se dau $Q$ întrebări. Pentru fiecare întrebare, primiți două numere $a$ și $b$ și trebuie să calculați:

Date de intrare

Se citesc de la tastatură:

• pe prima linie numărul $Q$;
• pe următoarele $Q$ linii câte două numere naturale $a$ și $b$.

Date de ieșire

Se afișează la ecran $Q$ linii.

Pe linia $i$ se va afișa răspunsul pentru întrebarea $i$, modulo $10^9+7$.

Restricții

• $1 \leq Q \leq 200 \ 000$;
• $4 \leq a \leq b \leq 1 \ 000 \ 000 \ 000$;
• rezultatul se cere modulo $M = 10^9+7$.

Exemplu

stdin

3
4 4
4 5
6 7

stdout

13
34
74

Explicație

• Pentru $[4,4]$ se cere $C(4)=13$.
• Pentru $[4,5]$ se cere $C(4)+C(5)=13+21=34$.
• Pentru $[6,7]$ se cere $C(6)+C(7)=31+43=74$.