You are given a table with n rows and m columns. You want to color each unit square of the table with one of the following three colors:
The condition to color the units is as follows:
Your task is to determine the number of ways you can color the table.
Input format
Output format
In T lines, print the answer for each test case that represents the number of ways you can color the table.
Constraints
1≤T≤1051≤n,m≤109
These are 4 valid ways of coloring a 1*1 table.