Unique Relief

mihassan #HelpFloodVictims Program...
Limits 1s, 512 MB

Thanos has now figured out how to visit all the houses in the flood-affected area. However, now he has to decide how to distribute the relief among them.

Thanos has collected N taka to distribute In the flood-affected area. He wants to make sure each family receives unique amount of relief. Each family should receive prime numbered taka and amounts received by any two families should not have any common divisor greater than 1. Also, Thanos needs to distribute all the money and he should try to give relief to as many families as possible.

Input

Inputs start with Testcase T For each case, there will be one number N total amount of relief amount.

1 ≤ T ≤ 104

1 ≤ N ≤ 104

Output

For each test case, print maximum number of family that can receive unique relief. If there is no way to distribute all relief amount, print 0.

Sample

InputOutput
4
2
4
17
19
1
0
4
3

Submit

Login to submit.

Statistics

67% Solution Ratio
Taran106Earliest, Aug '19
BalchalFastest, 0.0s
RamprosadGLightest, 131 kB
Ultra.NazmulShortest, 515B
Toph uses cookies. By continuing you agree to our Cookie Policy.