NGIRL - Namit In Trouble

no tags 

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 amountK.

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 likes.

Example

Input:
3
10 2
20 7
10 4

Output:
2 2
2 1
2 1

hide comments
a2j007: 2017-03-21 06:32:20

AC :)

Last edit: 2017-03-21 06:33:44
anmol23: 2017-03-18 07:44:34

How to avoid TLE

dwij28: 2017-03-14 16:45:15

Got some errors since I assumed (n >= k), it isn't mentioned anywhere so it was a mistake on my part. assert(n >= k) gives a runtime error. Be careful :)

shubhamsh09: 2017-03-14 11:42:35

i am getting TLE , how to avoid that ???

wisfaq: 2017-03-12 10:25:00

Come on, it's not that unintellegible. Question of reading. I've seen much worse examples.

Jacob Plachta: 2017-03-11 06:30:40

This problem is unintelligible, it took me forever to figure out what it's actually asking...

The first output value is the number of gifts which satisfy only the first condition (exactly 3 divisors).

The second output value is the number of gifts which satisfy both conditions (also greater than K).

benn: 2017-03-10 14:02:20

Can anyone explain me the second output?


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