Problem D

Number of Divisor

Problem Description

Given two integers X and Y, calculate how many numbers are there that divides XY. The term divide means that you can divides two integers without leaving any remainder.

For Example,

Let X = 6 and Y = 2.

XY is equal to 62, which is 36.

There are 9 numbers which divides 36, which are: {1, 2, 3, 4, 6, 9, 12, 18, and 36}

Input Speficication

The first line of input contains an integer T, the number of test cases follow.

Each test case consists of two integers X (1 <= X <= 1000) and Y (0 <= Y <= 6).

Output Speficication

For each case, print in a single line the number of divisor of XY in the format: “Number of divisor of <X^Y> is <P>.” (without quotes). See sample output for clarity.

2
6 2
10 1

Number of divisor of 36 is 9.
Number of divisor of 10 is 4.