Almost Prime是那些非質數，但是僅可以被一個質數整除的數。例如：8是一個Almost Prime，因為8只可以被2這個質數整除，而6不是Almost Prime，因為6可以被2和3整除。
你的任務是寫一個程式來找出在一特定範圍內Almost Prime的數目。
Input
輸入的第一列有一個正整數N，（N <= 600）代表以下有多少組測試資料。
每組測試資料一列，有2個正整數 low 和 high，（0 < low <= high <1012）。請參考Sample Input。
Output
對每組測試資料請輸出一列 。介於 low 和 high 之間（包含 low 和 high），共有多少個Almost Prime。
| Sample Input | Sample Output |
10 1 10 1 3 3 4 4 4 4 5 4 9 5 7 5 8 999999999998 999999999999 1 999999999999 |
3 0 1 1 1 3 0 1 0 80070 |