DCEPC203 - Obsession


Ankur sir is really obsessed with dce coders. Every other day he announces to the admins the current number of members and boasts about the continuous increase in the member count. Within a week the admins got bored of his habit and started losing interest in this topic. Ankur sir is very clever. He knows that every body loves to solve puzzles. To maintain their interest he decides to ask a puzzle based on the number of current members. This way he can still bug the admins about the increasing member count without making them feel bored. The puzzle says for the given member count N, tell me how how many smaller numbers (k ≥ 2) exist such that F(k) = 2 * k * k - 1 is a prime.

Input

First line gives T, the number of test cases

Each of the next T lines give a number N.

Output

Print the output for every test case on a new line   

Constraints

T ≤ 1000

2 ≤ N ≤ 10000000

Example

Input:
1
5

Output:
3

hide comments
fakesson: 2019-12-12 22:33:43

very similar to https://projecteuler.net/problem=216

[Lakshman]: 2015-06-28 21:02:48

I Have checked all inputs till 1e7 with My brute force.
7
10000000
1200975
1000000
141444
100000
17185
10000
2202
1000
303
100
45
10
6

--------------------------------
Process exited after 136.1 seconds with return value 0

The next big thing: 2015-06-28 16:46:38

Please help me i'm getting wa...submission ID 14557381

Someone please verify these test cases..

Input:
7
10
100
1000
10000
100000
1000000
10000000

Output:
6
45
303
2202
17185
141444
1200975

EDIT: Thanks Lakshman for verifying,but i still can't figure out the mistake in my code..:-(

EDIT2: Got ac!!! , i learnt something weird today..in codeblocks on my computer,it gave correct answer,but on ideone wa for large inputs..then i found in codeblocks,long ==long long,but in ideone,long ==int,due to overflow,it gave wa for large inputs,i changed everything to long long and got ac..:-)

Last edit: 2015-06-29 13:05:17
[Lakshman]: 2013-07-17 16:43:22

Need help can any one tell me what is the maximum value of f(k) ?..is it 2*10000000*10000000-1?

[Rampage] Blue.Mary: 2013-03-12 10:20:42

My solution is indeed very humble.

(Tjandra Satria Gunawan)(曾毅昆): 2012-09-29 17:21:50

My Brute-force solution: AC! yeah! :-D
Thanks a lot, for 20s time limit.. \(^_^)/

dce coders: 2012-03-11 12:41:51

@Mehmet: Input file is correct.
@Mitch: No,values of N can be in any order in the input file.

Mitch Schwartz: 2012-03-11 02:35:38

From the problem description, it seems we can assume the values of N are given in strictly increasing order in the input file. Is this true?

@Mehmet: The value I get for n=10^7 just from brute force is significantly lower than what you wrote.

mehmetin: 2012-03-08 18:54:58

Is there something wrong with the input? I'm getting TLE, can you check my submission with ID 6623040? I'm getting 4902128 for n = 10,000,000. Is that correct?

Last edit: 2012-03-08 18:56:29

Added by:dce coders
Date:2012-02-27
Time limit:2.355s
Source limit:3000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem