You are given a number X and K. break X into K parts (each part should be a positive integer) such sum of parts is X and the product of parts is maximum possible.

INPUT

The first line will contain t number of test cases.

Next t lines will contain two numbers X and K.

OUTPUT

For each line print single integer as a product of all the parts to modulo 100000007.

CONSTRAINTS

1 <= t <= 10

1 <=  K <=X <= 10⁵