PFACTORS - Pisano Factors

no tags 

Given an integer n.

Find how many integers c are there such that their Pisano period is a factor of n. 

1 <= c <= 10^5

There are multiple test cases.

Input

The first line contains number of test cases, 1 <=  t <= 100

Next t lines contain an integer n each. 1 <=  n <= 10^9

Output

Output the answer to each test case on a separate line.

Example

Input:
3
6
9
10

Output: 3
2
2

hide comments
queen_123: 2016-01-30 10:54:42

sarfaraz, there should be a number also include........pisano(3)=2

priyanka kumari: 2016-01-26 19:08:07

PLS EXPLAIN THE MEANING OF YOUR QUESTION

Bhuvnesh Jain: 2016-01-24 06:30:59

Please explain the test cases.

sarfaraz => there are 3 numbers whose pisano period is factor of 6. They are : pisano(1) = 1 , pisano(2) = 3 and pisano(4) = 6. Hence the answer for 6 is 3.

Last edit: 2016-01-24 11:23:02

Added by:sarfaraz
Date:2016-01-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY