Time Lord from Gallifrey, The Doctor, and his partner, Amy Pond have crash landed on a planet where there are a lot of Weeping Angels imprisoned. Weeping Angels are deadly creatures who can kill anyone just by looking at them.

Unfortunately for them, they find out that Weeping Angels have started to escape and have threatened all other species on the planet. The only way to save everyone is to make them teleport to some other planet.

A total of n teleporting pods are available there, and there are a total of k residents which have to be teleported. Each pod can carry one person at a time. Thankfully for them, k <= n always. Since there is not much time left, all k residents run towards these pods. All k residents have been assigned Social Security Numbers from 1, 2, 3, .... k and they occupy the pods, from beginning, in that particular order. Pods numbered k+1, k+2, ..., n are empty.

The teleporting pods are configured in such a way that all pods will be teleported to the new place, irrespective of whether the pod is empty or not.

Upon reaching the target planet, however, these pods rearrange themselves randomly.

What is the probability that upon reaching the target planet, the pods will be arranged in such a way that all k residents are in neighboring pods, that is, there is no empty pod between any two residents.

Output your answer as an integer, which is the required probability in percentage. If the answer is floating point, use the mathematical floor function to convert it to an integer. Example, if the answer is 76.2%, output 76. For 87.9325%, output 87.

Input

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

Each test case consists of exactly one line, with two integers n and k separated by a space, in that order.

Output

For each test case, output the total number of ways the stations can be occupied by the residents.

Output your answer as an integer, which is the required probability in percentage. If the answer is floating point, use the mathematical floor function to convert it to an integer. Example, if the answer is 76.2%, output 76. For 87.9325%, output 87.

Constraints

1 <= T <= 100

1 <= n, k <= 15

k <= n