Số đẹp được Nhật Tăng định nghĩa là số có tổng các ước của nó (không kể ~1~ và chính nó) lớn hơn nó.

• Ví dụ:
  • Ta xét số ~24~ có các ước ~1,2,3,4,6,8,12,24~.
  • Tổng của các ước không kể ~1~ và chính nó sẽ là : ~2 + 3 + 4 + 6 + 8 + 12 = 35~.
  • Vậy ~24~ là số đẹp vì ~35 > 24~.

Yêu cầu: Viết chương trình đếm xem từ ~1~ đến ~N~ có bao nhiêu số đẹp.

Input

• Dòng đầu chứa số nguyên ~T~ – số lượng câu hỏi. ~(T \leq 10^5)~.
• ~T~ dòng tiếp theo, mỗi dòng chứa ~1~ số nguyên dương ~N~ ~(N ≤ 10^6)~.

Output

• Ứng với mỗi câu hỏi, in ra ~1~ số nguyên thỏa mãn với yêu cầu của đề bài, mỗi số được in trên ~1~ dòng.

Sample Input

4
8
9
13
24

Sample Output

0
0
1
4