Trò chơi nhảy lò cò trong thời đại 4.0 được mô tả như sau:

• Bạn đang đứng tại vị trí n trên trục số tự nhiên (\(n \geq 2\))
• Bạn được nhảy đến vị trí nguyên \(x\) tùy ý nào đó thuộc đoạn \([1,n-1]\)
• Nếu \(x\) là ước của \(n\), bạn được cộng 1 điểm. Ngược lại thì bạn không được cộng điểm
• Nếu \(x = 1\) thì kết thúc trò chơi, ngược lại bạn tiếp tục chơi với \(n = x\)

Hãy tìm điểm số lớn nhất bạn có thể đạt được.

Input

• Dòng đầu chứa số lượng test: \(T\)
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên: \(n\)

Output

• Gồm \(T\) dòng là kết quả cho \(T\) test

Scoring

• \(1 \leq T \leq 1000\)
• Subtask \(1\) (\(30\%\) số điểm): \(2 \leq n \leq 1000\)
• Subtask \(2\) (\(30\%\) số điểm): \(1000 < n \leq 10^5\)
• Subtask \(3\) (\(40\%\) số điểm): \(10^5 < n \leq 10^{18}\)

Example

5
6
7
8
9
10 

2
2
3
3
3