Color the table

3

5 votes
Math Basic, Algorithms, Basic Math, Math
Problem

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:

  • Red
  • Blue
  • Black

The condition to color the units is as follows:

  • Each unit square of the table must contain two different colors and each color must occur twice.

Your task is to determine the number of ways you can color the table.

Input format

  • First line: One integer T denoting the number of test cases
  • Next T lines: Two space-separated integers n and m denoting the rows and columns of the table

Output format

In T lines, print the answer for each test case that represents the number of ways you can color the table.

Constraints

1T1051n,m109

Sample Input
2
1 1
3 3
Sample Output
18
373248
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

These are 4 valid ways of coloring a 1*1 table.

Editor Image

?