Mancunian, our favourite football fan, is a die-hard supporter of Manchester United Football Club. Being so, he is desperate to attend the grand unveiling of Jose Mourinho as the next manager of the club. But, his arch-nemesis Liverbird (who is a Liverpool fan) wants him to fail. Knowing that Mancunian is weak at mathematics, he has given him a problem to solve before the ceremony. Can you help Mancunian do it and thwart the evil plans of Liverbird?
A $$naughty \ number$$ is one whose number of distinct prime factors is equal to the number of digits in its decimal representation. The number $$1$$ is considered a naughty number.
Given $$Q$$ queries, each query specifying two integers $$a$$ and $$b$$, find the number of $$naughty \ numbers$$ lying between $$a$$ and $$b$$ (both included).
The first line contains an integer $$Q$$ denoting the number of queries.
Each of the next $$Q$$ lines consists of two integers $$a$$ and $$b$$ denoting the range for this query.
Print $$Q$$ lines. The $$ith$$ line contains the answer for the $$ith$$ query.
In the range $$1$$-$$10$$, all numbers except $$6$$ are naughty numbers.
In the range $$55$$-$$59$$, the naughty numbers are $$55$$, $$56$$, $$57$$ and $$58$$.
In the range $$100$$-$$105$$, only $$102$$ and $$105$$ are naughty numbers.