## Problem: Prime Factors and their Powers

*Difficulty: Easy

Given a number N, print all its unique prime factors and their powers in N.

```N = 100
Factor Power
2      2
5      2

N = 35
Factor  Power
5      1
7      1
```

Input:
The first line of input contains an integer T denoting the number of test cases.
The first line of each test case is N.

Output:
Print all prime factors and their powers separated by spaces.  The output should be printed in increasing order of prime factors.

Constraints:
1 ≤ T ≤ 200
2 ≤ N ≤ 10000

Example:
Input:
2
100
35

Output:
2 2 5 2
5 1 7 1
Implementation: Python 2.7, using Sieve Eratosthenes to generate a list of primes.

```from math import sqrt
def sieve_eratosthenes(n):
sieve = [True]*n
sieve[0] = sieve[1] = False
for i in xrange(int(sqrt(len(sieve)))):
if sieve[i]:
for j in xrange(i+i, len(sieve), i):
sieve[j] = False
return [i for i in range(len(sieve)) if sieve[i]]

primes = sieve_eratosthenes(10000)

def prime_factors_and_powers(n):
count, factors_powers = 0, {}
while n > 2:
power = 0
while n % primes[count] == 0:
power += 1
n /= primes[count]
if power > 0:
factors_powers[primes[count]] = power
count += 1
return factors_powers

if __name__ == '__main__':
t = input()
for _ in xrange(t):
n = input()
factors_and_powers = prime_factors_and_powers(n)
for key in sorted(factors_and_powers):
print key, factors_and_powers[key],
print

```