SP7301 LCKYCONT - Lucky Controller

Egor works as a controller in the bus. Each day he is given a pack of tickets which he then sells. Recently he has become interested about how many tickets in the pack are lucky. He thinks that the more tickets are lucky the luckier day he will have. No he wants to find out how lucky for him will the next day be. The numbers of all tickets consist of n digits. The ticket is considered to be lucky if the sum of the first n/2 digits equals to the sum of the last n/2 digits. Egor knows that the numbers in the pack that he will be given can start with equal probability from any number in the interval from a to b inclusive. The pack holds k tickets. The numbers in the tickets are consecutive. Help Egor find out the expected amount of lucky tickets in the pack.

The first line of the input file contain number n - the amount of tests. The next n lines consist of three integers a, b и k (0

Output the expected quantity of lucky tickets in the pack in the form of irreducible fraction. In case the result is an integer, no slash should appear in the output.