A factor tree is a binary tree where each non-leaf node p has two children q and r, such that p = q ∗ r and r ≠ 1, q ≠ 1. Prime factors are treated as leaf nodes of the tree.

Following are the factor trees of 24:

These are the four possible factor trees of 24.

Since Fredo loves doing experiment, he wants to know how many different factor trees are there whose root lies in the range [l, r] and the tree contains x as a node.

Two factor trees are different if and only if they are not isomorphic.

Two trees are called isomorphic if one of them can be obtained from other by a series of flips, i.e. by swapping left and right children of a number of nodes. Any number of nodes at any level can have their children swapped. Two empty trees are isomorphic.

These two trees are isomorphic.

The above four factor trees of 24 are different as they hold the above definition.

Fredo has written a program to know the different factor trees as asked in the question but he asks you to write a program to check whether he did it right or not.

Input

First line contains the number of test cases t ( 1 ≤ t ≤ 105). Each of the following t lines consists of three integers x (2 ≤ x ≤ 500), l, r (2 ≤ l ≤ r ≤ 5000) as described in the question.

Output

Print the number of different factor trees for each query in a separate line.