Lee tried so hard to make a good div.2 D problem to balance his recent contest, but it still doesn't feel good at all. Lee invented it so tediously slow that he managed to develop a phobia about div.2 D problem setting instead. And now he is hiding behind the bushes...

Let's define a Rooted Dead Bush (RDB) of level n as a rooted tree constructed as described below.

A rooted dead bush of level 1 is a single vertex. To construct an RDB of level i we, at first, construct an RDB of level i-1, then for each vertex u: 

  * if u has no children then we will add a single child to it; 
  * if u has one child then we will add two children to it; 
  * if u has more than one child, then we will skip it. 

<image> Rooted Dead Bushes of level 1, 2 and 3.

Let's define a claw as a rooted tree with four vertices: one root vertex (called also as center) with three children. It looks like a claw:

<image> The center of the claw is the vertex with label 1.

Lee has a Rooted Dead Bush of level n. Initially, all vertices of his RDB are green.

In one move, he can choose a claw in his RDB, if all vertices in the claw are green and all vertices of the claw are children of its center, then he colors the claw's vertices in yellow.

He'd like to know the maximum number of yellow vertices he can achieve. Since the answer might be very large, print it modulo 10^9+7.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases.

Next t lines contain test cases — one per line.

The first line of each test case contains one integer n (1 ≤ n ≤ 2 ⋅ 10^6) — the level of Lee's RDB.

Output

For each test case, print a single integer — the maximum number of yellow vertices Lee can make modulo 10^9 + 7.

Example

Input


7
1
2
3
4
5
100
2000000


Output


0
0
4
4
12
990998587
804665184

Note

It's easy to see that the answer for RDB of level 1 or 2 is 0.

The answer for RDB of level 3 is 4 since there is only one claw we can choose: \{1, 2, 3, 4\}.

The answer for RDB of level 4 is 4 since we can choose either single claw \{1, 3, 2, 4\} or single claw \{2, 7, 5, 6\}. There are no other claws in the RDB of level 4 (for example, we can't choose \{2, 1, 7, 6\}, since 1 is not a child of center vertex 2).

<image> Rooted Dead Bush of level 4.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class q_4 {
    static Scanner sc;
    static FastReader fr;
    static int mod = 1000000000+7;
    static int known = 4;
    public static void main(String[] args){
        sc = new Scanner(System.in);
        fr = new FastReader();
        int test = fr.nextInt();
        long[] xVals=  new long[((2*1000000)+1)];
        xVals[0] = xVals[1]= xVals[2]= 0;
        xVals[3] =xVals[4] = 4;
        for(int tt=0; tt<test; tt++){
            int n = fr.nextInt();
            if(n==0 || n==1){
                System.out.println(0);
                continue;
            }
            if(xVals[n]==0){
                xVals[n] = calcXVals(xVals, n);
            }
            System.out.println((xVals[n])%mod);
        }
    }

    private static long calcXVals(long[] xVals, int n) {
        for(int i=known+1; i<=n; i++){
            known++;
            long prev = xVals[i-1];
            long prevv = xVals[i-2];
            int count = 0;
            if(i%3==0){
                count=4;
            }
            xVals[i] = (((prev+(2*prevv))) + count)%mod;
        }
        return xVals[n];
    }


    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;

        public FastReader()
        {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }

    public static Integer[] getIntArrayFromSingleLine(){
        List<Integer> list = new LinkedList<>();
        String[] str = fr.nextLine().split(" ");
        for(String s: str){
            list.add(Integer.parseInt(s));
        }
        Integer[] arr = new Integer[list.size()];
        return list.toArray(arr);
    }

    public static Long[] getLongArrayFromSingleLine(){
        List<Long> list = new LinkedList<>();
        String[] str = fr.nextLine().split(" ");
        for(String s: str){
            list.add(Long.parseLong(s));
        }
        Long[] longs = new Long[list.size()];
        return list.toArray(longs);
    }

    public static Double[] getDoubleArrayFromSingleLine(){
        List<Double> list = new LinkedList<>();
        String[] str= fr.nextLine().split(" ");
        for(String s: str){
            list.add(Double.parseDouble(s));
        }
        Double[] doubles = new Double[list.size()];
        return list.toArray(doubles);
    }

    public static String[] getStringArrayFromSingleLine(){
        return fr.nextLine().split(" ");
    }

    public static int[] getArray(int n){
        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = fr.nextInt();
        }
        return arr;
    }

    public static long[] getLongArray(int n){
        long[] res = new long[n];
        for(int i=0; i<n; i++){
            res[i] = fr.nextLong();
        }
        return res;
    }

    public static double[] getDoubleArray(int n){
        double[] arr = new double[n];
        for(int i=0; i<n ; i++){
            arr[i] = fr.nextDouble();
        }
        return arr;
    }

    public static char[] getCharArray(){
        return fr.next().toCharArray();
    }

    public static String[] getStringArray(int n){
        String[] strings = new String[n];
        for(int i=0; i<n; i++){
            strings[i] = fr.next();
        }
        return strings;
    }

    // Get GCD
    public static int getGCD(int a, int b){
        return (a==0 ? b : getGCD(b%a, a));
    }

    public static int getGCD(int[] arr){
        int n = arr.length;
        if(n==0){
            return -1;
        }
        int res = arr[0];
        for(int i=1; i<n; i++){
            res = getGCD(res, arr[i]);
        }
        return res;
    }

    // Get all prime numbers till N using seive of Eratosthenes
    public static List<Integer> getPrimesTill(int n){
        boolean[] arr = new boolean[n+1];
        List<Integer> primes = new LinkedList<>();
        for(int i=2; i<=n; i++){
            if(!arr[i]){
                primes.add(i);
                for(long j=(i*i); j<=n; j+=i){
                    arr[(int)j] = true;
                }
            }
        }
        return primes;
    }


    // This method returns list of PrimeFactors of a number in O(sqrt(N));
    public static Map<Integer,Integer> getPrimeFactors(long n){
        Map<Integer,Integer> res = new HashMap<>();
        int sqrt = (int) Math.sqrt(n);
        if(n%2 == 0){
            int c = 0;
            while(n%2==0){
                c++;
                n/=2;
            }
            res.put(2,c);
        }
        for(int i=3; i<=sqrt; i+=2){
            if(n%i == 0) {
                int c = 0;
                while (n % i == 0) {
                    c++;
                    n /= i;
                }
                res.put(i,c);
            }
        }
        if(n!=1){
            res.put((int)n,1);
        }
        return res;
    }

}