You are given two integers and . You are interested in a rooted weighted tree with the following conditions.
Each edge has a weight of a positive integer.
For each vertex of the tree, there exists set of 's children of size than such that all the edges connecting and this set of children all have the same weight.
The diameter of the tree is not greater than . The diameter of a tree is the maximum distance between any two vertices.
Find the maximum number of vertices of such a tree. As the number of vertices can be very large, find the vertex count modulo .
输入格式
The first line contains an integer (), the number of test cases.
Each of the next lines contains two integers and () representing a case you have to solve.
输出格式
For each of the test cases, output a single line containing the maximum number of vertices modulo .
样例
样例输入 1
3
2 4
165 1
20 20
样例输出 1
12
2
891869870
数据范围与提示
The following illustrates, for the first case, a rooted tree with the maximum number of vertices.
:::