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}\)