题目描述

M国有一个习俗，巫师要对新出生的婴儿进行占卜，占卜的结果是一个字符串S和一个数字N。新生儿的名字从字符串S中长度为N的子串中选择。现在有T个新生儿，请你计算一下每个新生儿各能取多少个不同的名字。（M国的语言与我们不同，只有A~L十二个英文字母，且均为大写）

输入格式

第一行输入一个整数T,表示有T个婴儿。 接下来T行，每行输入一个字符串S，一个整数N，用空格隔开。

输出格式

输出单独占一行，输出新生儿能取到最多多少种不同的名字。

样例

输入样例1

2

ABABC 2

BBBBCCCC 3

输出样例1

3

4

数据范围与提示

1<=T<=100

1<=N<=6