You must construct a directed graph with exactly N nodes conveniently numbered between 1 and N. But this is not an ordinary graph; this is a special graph for which each node must have K or less directed edges going to their proper divisors (nodes numbered with those divisors values). If some node has only k ≤ K proper divisors, then that node will have exactly k edges to those k divisors. Also note that if some node has M > K proper divisors then that node will have exactly K edges to some group of K proper divisors of the M available. A proper divisor of some integer number P is any divisor of P, excluding P itself. For example, 1, 2 and 3 are proper divisors of 6; but 6 is not a proper divisor of itself. Given the value for K and the number of nodes N in the graph you must construct, can you find the number of edges on it after it is constructed? Also, can you determine the number of possible graphs which can be constructed fulfilling the above specifications? Input The first line contains an integer T (1 ≤ T ≤ 5∗105) representing the number of graphs to construct. The next T lines contain two integer numbers N and K (1 ≤ N, K ≤ 5∗103) representing the number of nodes in the graph and the maximum number of edges per node. Scenarios must be answered in the same order of the graphs given in the input. Output For each graph you must print a line containing two integer numbers representing the number of edges of the graph and the number of possible graphs which can be constructed, respectively. As those values could be large, print them modulo 1000000007 (109 + 7). Sample Input 3 42 53 62 Sample Output 41 51 73