Ayla is 11 years-old kid and she likes this beautiful number very much. Today, she prepared a new interesting problem for you based on 11. She gives you K and M, and you are required to find the number of positive integers having each digit (0 to 9) occurring exactly K times and giving M modulo 11. Surely, the number cannot have leading zeros.

Input

The first line of the input contains T denoting the number of test cases. Each of the next T lines contains K (1 ≤ K ≤ 2) and M (0 ≤ M ≤ 10).

Output

For each test case, print the number of positive integers satisfying Ayla`s condition.