Sum Of Factors

medium

Question Solve Solutions

Given a number n, output the summation of all its proper Factors.

Note: A proper Factor of a natural number is the divisor that is strictly less than the number.

Input Format

The first line contains integer t stating number of test cases. For next t lines, each line contains an integer n.

Output Format

In each of t lines, print the summation of Factors of the Integer given.

Constraints

1&lt;= t &lt;= 10^5
1&lt;= n &lt;= 10^5

Example

Input

Output

1
8
22

Relatively Prime Pairs

Chinese Remainder Theorem

Related Questions

medium Extended Euclidean Algorithm medium Linear Diophantine Equation hard Eulers Totient Function medium Wilsons Theorem medium Modular Fast Exponentiation medium Modular C(n,r) hard No Max No Min medium Prime Factors Using Sieve medium All Factors Using Sieve easy Count Of Common Divisors medium Gcd Length medium I Hate 1111 medium Relatively Prime Pairs easy Chinese Remainder Theorem easy Monkey Tradition