INS16G - Enough of GoT

no tags 

Given two integers N and P you need to find the sum of all positive integers less than or equal to N which have no divisor smaller than or equal to P apart from 1.

Input

The first line contains one integer T - denoting the number of test cases.

T lines follow each containing two space separated integers N and P.

Output

For each test case output the required sum in a new line.

Constraints

T <= 10

2 <= P <= N <= 2,000,000,000

example

Input:
4
11 7
10 10
4 2
7 2

Output:
11
0
3
15

hide comments
Scape: 2016-04-12 23:48:33

Yeah, please move this to tutorial because it is the same problem. Even the 900B source limit is identical.

(reply) => I did that on intention to avoid any precomputation! Anyway moved to tutorial.

Last edit: 2016-04-13 00:25:24
[Rampage] Blue.Mary: 2016-04-12 17:04:23

Isn't this (almost) the same as problem SUMPRIM1?

(reply) => Should I move this to tutorial ?

Last edit: 2016-04-12 19:44:38

Added by:Adarsh kumar
Date:2016-04-10
Time limit:0.100s-1.299s
Source limit:900B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:INSOMNIA 2016