DCEPCA08 - Saving BOB - 2

Alice and Bob devised a new game to play. Alice wrote an expression on the paper and started generating an array of numbers from that. She wrote the formula as

a[i] = (51 * a[i - 1] + 52) % 53 + 1

The array starts from index 1 and a[0]=1

Bob takes all the numbers from that array up to an index N also given by Alice. He makes all the subsets possible from that array. He calculates the sum of numbers in each of the subsets and finds which of the subset is prime. A subset is prime if the sum of numbers in the subset is a prime number. Bob gets boggled by the enormous size of array that Alice is generating and asking him to do this. Can you help Bob calculate the number of different prime subsets that can be made from the given array ?

Constraints

0 < T <= 100
0 < N <= 10^5

Input

It consists of T+1 lines were T is the number of test cases and N is the index of the array up to which Bob has to calculate. The array of the numbers can always be formed from the formula that Alice wrote.
Note : Array index starts from 1. Hence a[0] is not an element of the array.

Output

Print T lines each containing the number of different prime subsets that can be made from the array given.

Example

Input:
2
4
5

Output:
3
6

Added by:dce coders
Date:2012-12-04
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem

hide comments
2014-12-10 16:15:52 Min_25
Note:
"Calculate the number of different prime subsets that can be made from the given array" means "Calculate the number of primes which can be written as the sum of some subset (subsequence) of the array".

Last edit: 2014-12-10 16:43:07
2014-01-04 17:43:20 Waseem Alkafri
would you please, add more details about subset, what do you mean by subset in this problem
2013-01-06 21:44:59 (Tjandra Satria Gunawan)(曾毅昆)
strange, 32bit slower than 64bit...
2012-12-09 19:23:11 (Tjandra Satria Gunawan)(曾毅昆)
@Mario Ynocente Castro: Yes
2012-12-09 18:54:14 MarioYC
@tjandra: did you mean subsequence?
2012-12-07 16:01:54 (Tjandra Satria Gunawan)(曾毅昆)
@Francky: You're right, by the definition it's not subset... maybe it's sublist because {33,35,33,35} and {33,35} are considered different...
2012-12-07 15:42:43 Francky
I'm in trouble with "subset", as {33, 35, 33, 35} and {33, 35} are equal subset of {1..51}, I guess it's not what you ask for, it would be too easy. Please make some clarifications. Did you mean subset, sublist, slice, or other thing ?
2012-12-07 12:22:44 (Tjandra Satria Gunawan)(曾毅昆)
ok, done with this problem... 0,33s is my best :-D
It still can be faster if I can convert all data type to 32bit, but not now.. :-D

Last edit: 2012-12-07 14:52:42
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.