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.
3
1234567
1268501
1268499

788765312
999997375
999999350

import java.io.*;
import java.io.IOException;
import java.lang.Thread.State;
import java.util.*;
//import javafx.util.Pair; 
//import java.util.concurrent.LinkedBlockingDeque;




    
  public class Codeforces {
        
        public static long mod = (long)Math.pow(10, 9)+7 ;
        public static double epsilon=0.00000000008854;//value of epsilon
        public static InputReader sc = new InputReader(System.in);
        public static PrintWriter pw = new PrintWriter(System.out);
        
        public static ArrayList<ArrayList <Integer>> GetGraph(int n,int m){
            ArrayList<ArrayList <Integer>> g=new ArrayList<>();
            for(int i=0;i<n;i++){
                g.add(new ArrayList<>());
            }
            for(int i=0;i<m;i++){
                //int t=sc.nextInt();
                int u=sc.nextInt()-1;
                int v=sc.nextInt()-1;
                g.get(u).add(v);
                //if(t==0)
                g.get(v).add(u);
            }
            return g;
        }
        
        public static int find(int a,int p[]){
            if(a!=p[a]){
               p[a]=find(p[a], p);
            }
             return p[a];
        }
        public static void Union(int a,int b,int p[]){
            p[find(b, p)]=find(a, p);
        }
        public static long gcd(long a,long b){
            while(b>0){
                long t=b;
                b=a%b;
                a=t;
            }
            return a;
        }
        public static void dfs(ArrayList<ArrayList <Integer>> g,long val[],int u,int vis[],long m,int p[]){
            vis[u]=1;
            //boolean f=false;
            val[u]=1;
            for(int i=0;i<g.get(u).size();i++){
                int v=g.get(u).get(i);
                if(vis[v]==0){
                    p[v]=u;
                    dfs(g, val, v, vis,m,p);
                    val[u]*=(val[v]+1);
                    val[u]%=m;
                }
                
            }
            vis[u]=2;
        }
        public static void dfs1(ArrayList<ArrayList <Integer>> g,long val[],int u,int p[],long m,long ans[],long up[]){
           // vis[u]=1;
            //boolean f=false;
            ans[u]=(val[u]*(up[u]+1))%m;
            int n=g.get(u).size();
            long pre[]=new long [n];
            long suf[]=new long [n];
            long k=1;
            for(int i=0;i<n;i++){
                int v=g.get(u).get(i);
                if(v!=p[u]){
                    k*=(val[v]+1);
                    k%=m;
                }
                pre[i]=k;
            }
            k=1;
            for(int i=n-1;i>=0;i--){
                int v=g.get(u).get(i);
                if(v!=p[u]){
                    k*=(val[v]+1);
                    k%=m;
                }
                suf[i]=k;
            }
            
            for(int i=0;i<g.get(u).size();i++){
                int v=g.get(u).get(i);
                 k=1;
                if(i>0){
                    k*=pre[i-1];
                    k%=m;
                }
                if(i<n-1){
                    k*=suf[i+1];
                    k%=m;
                }
                if(v!=p[u]){
                    k*=(up[u]+1);
                    k%=m;
                    up[v]=k;
                    dfs1(g, val, v, p, m, ans, up);
                }
                
            }
        }
        
    public static long modu(long p,long mod){
        if(p>=mod){
             p=-mod;
        }
        return p;
    }
    public static long pow(long x,long y,long mod){
		long ans=1;
		while(y>0){
			if((y&1)==1){
				ans=(ans*x)%mod;
			}
			y=y>>1;
			x=(x*x)%mod;
		}
		return ans;
    } 
	 public static void rec(int mask,int i,ArrayList<Integer> not,int groupmask,long val[],long dp[]){
        if(i==not.size()){
            dp[(mask|groupmask)]=Math.max(dp[(mask|groupmask)], dp[mask]+val[groupmask]);
            return;
        }
        rec(mask, i+1, not, groupmask, val, dp);
        rec(mask, i+1, not, groupmask|(1<<not.get(i)), val, dp);
     }
        public static void main(String[] args) {
            // code starts..
            int n=2000000;
            long dp[][]=new long[n+1][4];
            dp[1][0]=1;
            for(int i=2;i<=n;i++){
                dp[i][2]=dp[i-1][2]+dp[i-1][1];
                dp[i][1]=dp[i-1][0];
                dp[i][0]=2*dp[i-1][1]+dp[i-1][0];
                dp[i][0]%=mod;dp[i][1]%=mod;dp[i][2]%=mod;
               dp[i][3]=2*dp[i-2][3]+dp[i-1][3]+((i%3==0)?4:0);
               dp[i][3]%=mod;
               //pw.println(Arrays.toString(dp[i]));
            } 
           int q=sc.nextInt();
           while(q-->0){
            n=sc.nextInt();
            //long k=4*(dp[n][2]/2+dp[n][2]%2);
            pw.println(dp[n][3]); 
           }
            // Code ends...
            pw.flush();
            pw.close();
        }
       
        public static Comparator<Integer[]> column(int i){
            return 
            new Comparator<Integer[]>() {
                @Override
                public int compare(Integer[] o1, Integer[] o2) {
                    return o1[i].compareTo(o2[i]);//for ascending
                    //return o2[i].compareTo(o1[i]);//for descending
                }
            };
        }
        public static Comparator<Pair> C(){
            return 
            new Comparator<Pair>() {
                @Override
                public int compare(Pair o1, Pair o2) {
                    return o2.le-o1.le;//for des
                }
            };
        }
        
        public static Comparator<Integer[]> pair(){
            return 
            new Comparator<Integer[]>() {
                @Override
                public int compare(Integer[] o1, Integer[] o2) {
                    int result=o1[0].compareTo(o2[0]);
                    if(result==0)
                    result=o1[1].compareTo(o2[1]);
                    return result;
                }
            };
        }
        
        public static String reverseString(String s){
            StringBuilder input1 = new StringBuilder(); 
            input1.append(s);  
            input1 = input1.reverse();
            return input1.toString();
        }
        public static int[] scanArray(int n){
            int a[]=new int [n];
            for(int i=0;i<n;i++)
            a[i]=sc.nextInt();
    
            return a;
        }
        public static long[] scanLongArray(int n){
            long a[]=new long [n];
            for(int i=0;i<n;i++)
            a[i]=sc.nextLong();
    
            return a;
        }
        public static String [] scanStrings(int n){
            String a[]=new String [n];
            for(int i=0;i<n;i++)
            a[i]=sc.nextLine();
    
            return a;
        }
        
    }
    
    class InputReader {
    
            private final InputStream stream;
            private final byte[] buf = new byte[8192];
            private int curChar, snumChars;
            private SpaceCharFilter filter;
    
            public InputReader(InputStream stream) {
                this.stream = stream;
            }
    
            public int snext() {
                if (snumChars == -1)
                    throw new InputMismatchException();
                if (curChar >= snumChars) {
                    curChar = 0;
                    try {
                        snumChars = stream.read(buf);
                    } catch (IOException e) {
                        throw new InputMismatchException();
                    }
                    if (snumChars <= 0)
                        return -1;
                }
                return buf[curChar++];
            }
    
            public int nextInt() {
                int c = snext();
                while (isSpaceChar(c)) {
                    c = snext();
                }
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = snext();
                }
                int res = 0;
                do {
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = snext();
                } while (!isSpaceChar(c));
                return res * sgn;
            }
    
            public long nextLong() {
                int c = snext();
                while (isSpaceChar(c)) {
                    c = snext();
                }
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = snext();
                }
                long res = 0;
                do {
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = snext();
                } while (!isSpaceChar(c));
                return res * sgn;
            }
    
            public int[] nextIntArray(int n) {
                int a[] = new int[n];
                for (int i = 0; i < n; i++) {
                    a[i] = nextInt();
                }
                return a;
            }
    
            public String readString() {
                int c = snext();
                while (isSpaceChar(c)) {
                    c = snext();
                }
                StringBuilder res = new StringBuilder();
                do {
                    res.appendCodePoint(c);
                    c = snext();
                } while (!isSpaceChar(c));
                return res.toString();
            }
    
            public String nextLine() {
                int c = snext();
                while (isSpaceChar(c))
                    c = snext();
                StringBuilder res = new StringBuilder();
                do {
                    res.appendCodePoint(c);
                    c = snext();
                } while (!isEndOfLine(c));
                return res.toString();
            }
    
            public boolean isSpaceChar(int c) {
                if (filter != null)
                    return filter.isSpaceChar(c);
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
            }
    
            private boolean isEndOfLine(int c) {
                return c == '\n' || c == '\r' || c == -1;
            }
    
            public interface SpaceCharFilter {
                public boolean isSpaceChar(int ch);
            }
        }
        class Pair{
            int le;
            int p;
            Pair(int leaves,int parent){
                le=leaves;
                p=parent;
            }
        }
        
        
        