Bhavik and Anurag are best and special friends, special in the sense that they both share their birthdays i.e. June 6. Ironically, neither of them gives each other friends birthday party owing to that fact.

Abhishek (aka "Guttss") being a clever friend of both wants to have a party from either of them so he decided to present a problem on 'hypercubes'. (Abhishek loves maths as you know!). They cannot ignore what "Guttss" has to say hence they need to solve the problem or give him a party!!

Here is the problem:

A cube is an object that measures the same distance across in three perpendicular directions in a three-dimensional space.

A four-dimensional hypercube is an object that measures the same distance across in four perpendicular directions in a 4-d space.

Given dimension i, create a hypercubic array using 1x1x....x1 (i times) hypercubes to form a big hypercube of side n.

Problem is to find the total number of 1x1x1...x1 (i times) hypercubes on the surface of big hypercube.

Bhavik being his lazy self wants to sleep as well as solve this problem before Anurag does as who first solves the problem avoids giving birthday treat to "Guttss".

Help Bhavik solve the problem so that he can sleep peacefully by avoiding a treat:))

Input

t=number of testcases (<2000)

next t lines: two integers n and i. (3<=n, i<=100)

Output

For each testcase print in newline the required answer.

Example

Input:
1
3 3

Output:
26

Explanation:

Take a Rubik's cube (3x3x3 cubic array of 1x1x1 cubes) and count.:)

Note: A cube is a hypercube in 3-D.

          Hypercubic arrays are made using 1x1x...x1 (i dimensions) hypercubes.

Warning:Time limit allows slower languages (java, python) to pass easily. However for faster languages (C/C++) answer might not fit in 64-bit.