_{This problem is a programming version of Problem 179 from projecteuler.net}

Find the number of integers , for which and have the same number of positive divisors. For example, has the positive divisors , , , while has , , , .

**Input Format**

First line of input contains single integer which is the number of testcases. All of the following lines contain single integer each.

**Constraints**

**Output Format**

For each testcase output the only integer which is the answer to the problem.

**Sample Input 0**

```
3
3
15
100
```

**Sample Output 0**

```
1
2
15
```

**Explanation 0**

The only are and .