Maniac Moroney wants to get a wall in his room painted on account of his birthday! However, living up to his nature , he has put up multiple conditions for the painters:
1: The wall must be painted only in strips of red, blue and white colour.
2:Strips of the same color cannot be placed next to each other.
3:A blue strip must always be placed between a white and a red or between a red and a white one.
Your task is to determine the number of ways in which the wall can be painted.
Input:
The first line contains an integer T that denotes the number of test cases. Next T lines follow,each of which contains an integer N, the number of the stripes.
Output:
On a separate line output an integer denoting the number of the ways in which he can paint the wall %(10^9+7).
Constraints:
1 ≤ T ≤ 100.
1 ≤ N ≤ 100.