拒绝七年之痒

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

messIDou和他的女友恩恩爱爱已经五年,但他的舍友yxcwudi出于羡慕嫉妒恨,老是诅咒他们会"七年之痒",所以messIDou对“7”这个数字格外反感。即使买彩票的时候,与7有关的数字他也不会选。“与7有关”有如下定义: 1、数字的每一位的和含有7或为7的倍数(例:数字158.每一位的和1+5+8=14,是7的倍数) 2、数字本身含有7或为7的倍数(例:数字27.数字本身含有7) 我们知道,彩票有很多不同的玩法。对于n选m玩法即从1-n之间选择m个数。聪明的你,请帮messIDou算出,他到底有多少种不同的买法,与7有关的数可不在他的考虑范围内哦。

Input

第一行为t。表示下面有t组输入。 n,m(n和m均为正整数,且n≤40,m≤5){哇!好小的数,甚至能直接把所有与7有关的数写出来}

Output

拒绝“与7有关”的数,有多少种购买彩票方案

Sample Input

4
1 1
7 3
7 5
3 5

Sample Output

1
20
6
0

Hint

Source

StSky

提交代码