We will call n-cube of size c a hypercube in dimension n of length c.

Given N couples of two integers n and c, return the number of unique n-cubes and of n-rectangles (that aren’t n-cubes) that we can extract from the n-cube of length c.

Input

• 100 ≤ N ≤ 1000
• 2 ≤ n ≤ 10
• 1 ≤ c ≤ 100

Exemples

Input :

2 1
3 2
4 3

Output :

1 0
9 18
98 1198