Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Unique Relief

By mihassan · 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.

Samples

InputOutput
4
2
4
17
19
1
0
4
3


Discussion
Submit

Login to submit