Tianjin University Online Judge
Contests Virtual Contests Problems Submit Runs Status Rank List Forum

2783.   Amicable Pairs
Time Limit: 1.0 Seconds   Memory Limit: 65536K
Total Runs: 403   Accepted Runs: 190



A pair of integers (a,b) is called an amicable pair if the sum of the proper divisors of a equals b, and vice versa. For example, (220, 284) is an amicable pair, since the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110, and 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284, while the proper divisors of 284 are 1, 2, 4, 71 and 142 and their sum is 220.

Given K, output the number of different amicable pairs (a,b) where 1 ≤ aK and 1 ≤ bK. Note that (a,b) is considered the same pair as (b,a).

Input

The first line is an integer T, number of test cases. T lines follow, each contains an integer K.

Output

For each case, output on a line the number of different amicable pairs satisfying the constraint above.

Notes

  • Integer a is a proper divisor of b if 0 < a < b and there exists some integer k such that a * k = b.
  • Constraints

  • 1 ≤ T ≤ 1000
  • 1 ≤ K ≤ 100000
  • Sample Input

    2
    220
    284
    

    Sample Output

    2
    3
    

    Sample Input/Output Clarification

    The first three amicable pairs are (6,6), (28,28) and (220, 284).



    Source: The 5th UESTC Programming Contest Preliminary
    Submit   List    Runs   Forum   Statistics

    Tianjin University Online Judge v1.3.0
    Maintance:Fxz. Developer: SuperHacker, G.D.Retop, Fxz