Problem ID:
divgame
Points:
2.3 (partial)
Time limit:
1.5s
Memory limit:
64M
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, Golang, Java, Pascal, Perl, Python, Rust
Pusheen là một chú mèo rất thích số nguyên tố. Thế nên một ngày nọ, cô giáo đã đố Pusheen bằng một trò chơi về số nguyên tố.
Luật trò chơi như sau: cô giáo nêu ra một số ~N~ nguyên dương bất kì, ở mỗi bước, Pusheen sẽ chia số ~N~ hiện tại cho một số nguyên tố ~K~ bất kì (với điều kiện ~N~ chia hết cho ~K~), Pusheen sẽ thực hiện hành động này nhiều lần cho đến khi nhận được một số nguyên tố. Số điểm mà Pusheen nhận được sẽ là số giá trị khác nhau mà Pusheen có thể biến đổi được từ số ~N~.
Bạn hãy tìm số điểm tối đa mà Pusheen có thể nhận được.
Dữ liệu vào
Gồm ~T~ dòng, tương ứng với ~T~ testcase, mỗi dòng ghi số nguyên dương ~N~.
Dữ liệu ra
Gồm ~T~ dòng, mỗi dòng ghi số điểm tối đa mà Pusheen có thể nhận được ở testcase đó.
Giới hạn
- Subtask 1 (50%): ~N ≤ 10^7, T ≤ 5~.
- Subtask 2 (40%): ~N ≤ 10^{15}, T ≤ 5~.
- Subtask 3 (10%): ~N ≤ 10^7, T ≤ 10^5~.
Sample Input
3
4096
20
1246
Sample Output
1
2
3
Comments