SPOJ.com - Problem DCEPC203

DCEPC203 - Obsession

#sieve

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

Submit solution!

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 21000000010000000-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

Submit solution!

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