CUBE - HYPERCUBES


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.


hide comments
David: 2021-02-26 04:53:11

@lilpeep - The requirement of the problem is that the 1x hypercubes are on the surface of big hypercube. In 3 dimensions of a 3x3x3 cube, the center cube is not on the surface. Therefore, 3*3*3-1 = 26.

lilpeep: 2020-03-28 15:19:21

I counted rubiks cube 3x3x3 and it was not 26 ! :V help.
It was 27

Last edit: 2020-03-28 15:23:01
edyduk1234567: 2019-07-03 06:59:06

blyt

nadstratosfer: 2017-11-15 02:22:32

mahilewets, for us mortals with 3-dimensional imagination it is a difficult problem. Deriving a formula is easy once presented with some results, but to get there one needs to do some research or be familiar with multidimensional geometry.

mahilewets: 2017-09-10 20:54:35

Implementation difficulty 23 percent???
Are you kidding?! It is zero-difficulty I think.

Idea difficulty one percent??? What? It is at least more hard.

candide: 2017-04-10 22:04:11

Simple formula. Poor description, poor example, poor writing. Context character (Bhavik, etc) is just noise. Hypercube description is irrelevant (what difference with a hypersphere?). Hypercube term remains undefined, the same for the hypercube "surface". For a better understanding, try online SPOJ toolkit.

Last edit: 2017-04-11 09:35:59
Siddharth Singh: 2016-02-08 07:20:36

Too Easy in Python (PyPy 2.6)

Vamsi Krishna Avula: 2014-12-14 07:27:16

uff!, atlast AC in C++

Tanmay: 2014-06-07 09:16:31

Can someone post answer for some test cases? Say, 4 5?

Edit: Oops, my program was correct all along. Just I had exchanged the values of n and i while taking the input. -_-
Nice problem, especially for python! :P

Last edit: 2014-06-07 09:57:16
Stanley Pham: 2014-06-06 11:06:15

Yes, too easy for Python users :3


Added by:Bhavik
Date:2014-06-05
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Cube trilogy films