携程——聪明的猴子 （容斥定理）

Problem Description

森林中有一排香蕉树（无限长），一只猴子站在其中一棵树上，猴子在跳跃前要先抽取一张卡片，卡片上写有A+1个自然数，其中最后一个是B，前A个数只能小于等于B，卡片上的数字可以相同。猴子每次跳跃先从卡片上任选一个自然数C，然后向左、或向右跳C棵树。猴子的任务是：跳到与它左边相邻的香蕉树上时，就可以吃掉上面的香蕉。

例如，当A=2，B=4时，对于卡片(2, 3, 4)，猴子就可以吃到香蕉：它可以先向左跳3棵树，再向右跳两棵树。而对于卡片(2, 2, 4)，猴子则怎么也不可能跳到它左边相邻的香蕉树上。 

当确定A和B后，则一共可以有B^A张不同的卡片。问题是，在这所有的卡片中，有多少张可以让猴子完成任务。 

Input

第1行k,表示有k组测试数据，k<=100
第2至k+1行，每行两个自然数A和B，以一个空格分开 （A<= 10 , B <= 20)。

Output

共k行，每行的数字代表每组数据中，可以让猴子跳到它左边相邻香蕉树的卡片数。

Sample Input

3
2 3
4 8
5 13

Sample Output

8
3840
371292

题解：因为每一次从卡片选一张出来。就是说。每一张卡片都可以被选择不限定次数。

则x1*ak[1]+x2*ak[2]+……+xn*ak[n] +xn+1*m = 1

则可知ak[1]……ak[n],m之间一定不能有互质的数。。

所以我们先求出不符合的情况。就是说ak[1]……ak[n],m之间的两两有约数大于1。。

则他们有共同的约数。。这些约数只能是质数。。（因为不是质数的约数可以分割成质数相乘。如6 = 2*3）

2 3 5 7……。就是m的所有质约数。。

然后求出共同是2约数的个数。3的个数。。等等。但是还要减去重合的现象。。比如6的个数。。

这就要用到容斥定理。。