Joey and Chandler have a sheet of paper on which there are N empty squares arranged in a line and numbered from 1 to N. They wish to colour these squares with the crayons they have. Joey will colour all the squares numbered from 1 to K (both inclusive) and Chandler will colour all the squares numbered from K+1 to N (both inclusive).

They both have 10 crayons each, each crayon being of a different colour. One of these 10 crayons is White coloured. They have to fill colours in all these squares such that atleast one of the squares coloured by each of them is not white in colour so that the entire stretch on N squares has a minimum of two colourful (non-White) squares.

Given N and K, you have to report the total number of different possible appearances of the stretch of N squares i.e., the total number of different ways in which all the squares can be coloured.

Input

The first line consists of T denoting the number of test cases. The next T lines are such that each line consists of 2 space separated integers N and K.

Output

Print a single integer, the answer to each test case on a new line.

Constraints