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
rkp: 2018-01-21 14:26:02

Good problem.

Last edit: 2018-01-21 15:05:53
jh0n_12358: 2017-12-04 05:20:14

AC in One Go (TIme 0.00)

testing java: 2017-09-11 14:12:52

Dear author of this problem, Is there any particular reason for so tight time limit? Is there any non optimal solution which requires so strict time limit to make it invalid or is it just pure hate towards java programming language?

singlasahil221: 2017-08-21 07:38:01

AC after 2 w.a.
just missed one test case!!!

nikhil_ankam: 2017-04-04 11:02:07

Simple AC in one go:)

Thotsaphon Thanatipanonda: 2017-04-01 16:32:43

Can you change time limit from 0.009s-0.100s to 0.09s-0.100s for Java language?

KD : 2017-03-28 08:55:16

AC :) After 2 W.A. Nice question.......

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 :)


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