Namit's girlfriend's birthday is coming next week. He went to a gift shop and saw N gifts are arranged in a single row in such a way that the position at which the gift is placed is equal to its price. (Position starts from 1.)

Namit's girlfriend being a maths student like those numbers which have exactly 3 divisors, so Namit decide to buy only those gifts which are placed at a position which have only 3 divisors, but Namit's girlfriend likes gifts whose price are above a certain amount K.

Now Namit wants to know total choices he have and how many gifts his girlfriend like for a given value of N.

Input

Input starts with 1 ≤ T ≤ 1000 (number of test cases). Then T lines follows each containing two integer 1 ≤ N < 10¹⁰ (number of gifts at gift shop) and 1 ≤ K ≤ 10¹⁰.

Output

You program should output two values indicating total number of choices and the number of gifts Namit's girlfriend likes.

Example

Input:
3
10 2
20 7
10 4

Output:
2 2
2 1
2 1