Divisor Count

For each of up to 10 values of n below 10000, print n and its divisor count.

Easy2Number theoryBrute forceInterviewNo attempts yetTime limit2sMemory limit512 MB

Description

Examples1

Problem

Given an integer $n$ , count the divisors of $n$ .

A divisor is an integer $d$ with $1 \le d \le n$ that divides $n$ evenly.

For example, if $n$ is $10$ , the divisors are $1$ , $2$ , $5$ , $10$ , so the answer is $4$ . If $n$ is $9973$ , the number is prime, its only divisors are $1$ and $9973$ , and the answer is $2$ .

Input

The first line contains the count of numbers to process, $C$ . ( $1 \le C \le 10$ )

Each of the next $C$ lines contains one integer $n$ . ( $1 \le n < 10000$ )

Output

For each integer $n$ , print one line with $n$ , a single space, and the number of divisors of $n$ .