Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Birthday Cake
Time Limit: 5000MSMemory Limit: 65536K
Total Submissions: 1081Accepted: 418

Description

Prince Remmarguts helped Uyuw successfully hold a concert in our previous story (POJ 2451), and ...that was the day of Uyuw's birthday.

Ting-a-ling, the chef was called on by Remmarguts. "You must prepare an immense birthday cake for lovely Princess Uyuw in a single day," said Remmarguts. Though Remmarguts' order is outrageous, the chef eventually rushed to buy flour, sugar, fat, and some other ingredients.

There had been chaos caused by war for quite a long time. The price of everything has been highly raised. Being the head accountant of country UDF – United Delta of Freedom, you must weight the cake carefully to make sure the chef did not perform a cheat on the ingredients.

The cake is made up of N levels. There is a 'cube' in each level, while the length of cube on k-th level (count from the topmost) is exactly k! For Remmarguts lives in an M-Dimension world unlike our, you should notice that the 'cube' here means M-Dimension cube, and the volume of a cube with length k is k ^ M.

You are to calculate the total volume of such an immense cake.

Input

You should read the number of test cases Z (Z <= 30) in the first line. Each of the following lines denotes a single test case, consisting of two integers N and M. We guarantee that 1 <= N <= 10 ^ 41 and 3 <= M <= 100.

Output

Output one line per test case, showing the total volume of that cake. We also guarantee that the volume is less than 10 ^ 250.

Sample Input

2
3 3
6 5

Sample Output

36
12201

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator