Factor Trees#4040
A factor tree is a binary tree where each non-leaf node has two children and , such that p = q \cdot r and r \neq 1, q \neq 1. Prime factors are treated as leaf nodes of the tree.
Following are the factor trees of :
These are the four possible factor trees of .
Since Fredo loves doing experiment, he wants to know how many different factor trees are there whose root lies in the range [, ] and the tree contains 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 are different as they hold the above definition.
Write a program that counts the number of different factor trees.
First line contains the number of test cases (1 \le t \le 10^5). Each of the following lines consists of three integers (2 \le x \le 500), , (2 \le l \le r \le 5000) as described in the question.
Print the number of different factor trees for each query in a separate line.
Example 1