A boolean function is a function of the form f: B_n -> B, where B = {0, 1} and n is a non-negative integer called the arity of the function. Some Boolean functions are projections: p_n^k(x₁, ..., x_n) = x_k. And given an m-ary function f, and n-ary functions g₁, ..., g_m, we can construct another n-ary function: h(x₁, ..., x_n) = f(g1(x₁, ..., x_n), ..., gm(x₁, ..., x_n)), called their composition.

The Chef has formed a very nice planar graph out of icing on his latest cake. The nodes of the graph are represented by distinct points on the cake and every edge is drawn as a straight line segment between its two endpoints. For each edge e = (u,v) the line segment connecting u and v does not pass through any other point representing some other node. Finally, if two line segments representing different edges e,e' share a common point on the cake, it must be that this common point is in fact a common endpoint v of both e and e' (i.e. no two edges cross).

For a given positive integer N find the number of all pairs (a, b) of positive integers such that 1 <= a < b <= N and the sum a + b divides the product a * b.

Input

The first line contains a single positive integer T <= 5, the number of test cases. T test cases follow. The only line of each test case contains a positive integer N <= 10⁹.

Output

For each test case, output a single line containing the answer for the corresponding test case.

You have a tree (an acyclic, connected graph) with edge weights, but it is far too big. You are to prune the tree by deleting some edges so that the following property holds. For each connected component C of the pruned tree, there is some node r_C such that for every node v in C, the total weight of the edges on the path between v and r_C is at most some given value d.

You happen to like heavy trees so you want to delete the minimum possible total edge weight to satisfy this property.

Input