因为未来杯要比赛了，所以我们要研究未来数，未来数的定义如下：

1. 该数非素数。
2. 该数可以分解为2个素数的乘积
比如：
4是未来数，因为 4=2 * 2
21是未来数，因为 21=3 * 7
30不是未来数，因为 30=2 * 3 * 5
73不是未来数。因为 73 本身即是素数。

输入 l 和 r ，请你输出 [l,r] 闭区间中有多少个未来数

第一行输入一个正整数 t ，代表有 t组测试数据 ，每组测试数据有两个正整数 l 和 r ，用空格隔开。 1≤t≤10^5 1≤l≤r≤10^6

输出t行，每行1个整数