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
| Input | Output |
|---|---|
4 2 4 17 19 | 1 0 4 3 |
