You are given a function $f(n) = 2 \times 7^{n/2} \times \cos(n\theta) + n \times 4^n$, where $\theta = \tan^{-1}{\frac{\sqrt3}{2}}$.

You are also given two integers $p$ and $q$. Your task is to find the value of $\sum _\limits{n=p}^{n=q}f(n)$ (modulo $10^9+21$).

Input format

• The first line consists of an integer $T$ denoting the number of test cases.
• Each of the next $T$ lines consists of two space-separated integers $p$ and $q$.

Output format

Print $T$ lines each containing a single integer corresponding to the required value $\sum _\limits{n=p}^{n=q}f(n)$. Print the answer modulo $10^9+21$.

Constraints

$1\le T \le 10^2\\ 0\le p \le q \le 10^{18}$