NGIRL - Namit In Trouble

no tags 

Namit's girlfriend 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^10 (number of gifts at gift shop) and 1<=K<=10^10.

Output

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

Example

Input:
3
10 2
20 7
10 4
Output:
2 2
2 1
2 1

hide comments
auler_: 2020-06-26 16:18:21

You do not need binary search. Simple sieve gave me AC

sangmai: 2020-05-31 04:42:57

I can't understand the problem statement.

amdee07: 2020-05-21 08:56:58

just take constraint 10^5 i.e. (10^5)^2<=10^10.
Hope this will help in TLE.
(sieve + binary search +binary search).

deependra_18: 2020-04-14 06:44:18

thanks @avasthiayush k>n cost me 3 WA .

avasthiayush: 2020-04-02 13:07:50

Must consider the condition when k>n :)

lx_lovin: 2020-01-08 18:25:38

Sieve Of Eratosthenes + Binary Search -> AC

zarif_2002: 2019-11-04 11:48:32

Runs in my pc but gives compilation error here.

cyber_wizard: 2019-06-06 18:27:13

Can someone explain the question by explaining this test case

dewa251202: 2018-09-28 13:50:55

AC in one go too :)

uvshuvo: 2018-06-15 16:40:56

Nice problem AC in one go (time 0.00) thanks.


Added by:JUNK
Date:2017-03-06
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own Problem