Chef's company wants to make ATM PINs for its users, so that they could use the PINs for withdrawing their hard-earned money. One of these users is Reziba, who lives in an area where a lot of robberies take place when people try to withdraw their money. 
Chef plans to include a safety feature in the PINs: if someone inputs the reverse of their own PIN in an ATM machine, the Crime Investigation Department (CID) are immediately informed and stop the robbery. However, even though this was implemented by Chef, some people could still continue to get robbed. The reason is that CID is only informed if the reverse of a PIN is different from that PIN (so that there wouldn't be false reports of robberies).
You know that a PIN consists of $N$ decimal digits. Find the probability that Reziba could get robbed. Specifically, it can be proven that this probability can be written as a fraction $P/Q$, where $P \ge 0$ and $Q > 0$ are coprime integers; you should compute $P$ and $Q$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains a single integer $N$ denoting the length of each PIN. 

-----Output-----
For each test case, print a single line containing two space-separated integers — the numerator $P$ and denominator $Q$ of the probability.

-----Constraints-----
- $1 \le T \le 100$
- $1 \le N \le 10^5$

-----Subtasks-----
Subtask #1 (10 points): $N \le 18$
Subtask #2 (20 points): $N \le 36$
Subtask #3 (70 points): original constraints

-----Example Input-----
1
1

-----Example Output-----
1 1

-----Explanation-----
Example case 1: A PIN containing only one number would fail to inform the CID, since when it's input in reverse, the ATM detects the same PIN as the correct one. Therefore, Reziba can always get robbed — the probability is $1 = 1/1$.

Difficulty: EASY
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
try:
	T = int(input())
	for _ in range(T):
		N = int(input())
		print(1, 10 ** int(N / 2))
except:
	pass


import math
tt = int(input())
for i in range(tt):
	n = int(input())
	b = math.ceil(n / 2)
	nu = 10 ** b
	de = 10 ** n
	q = math.gcd(nu, de)
	print(nu // q, de // q)


for u in range(int(input())):
	n = int(input()) // 2
	print('1 1' + '0' * n)


T = int(input())
for i in range(T):
	n = int(input())
	print(1, 10 ** (n // 2))


for _ in range(int(input())):
	n = int(input())
	print(1, 10 ** (n // 2))


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
for _ in range(t):
	n = int(input())
	q = '1' + '0' * (n // 2)
	print(1, q)


from sys import stdin, stdout
from math import floor
ans = []
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	ans.append(f"1 {'1' + '0' * floor(n / 2)}")
stdout.write('\n'.join(ans))


for _ in range(int(input())):
	n = int(input())
	q = '1' + '0' * (n // 2)
	print(1, q)


i = 1
t = input()
while i <= int(t):
	n = int(input())
	n = n // 2
	print('1 1' + '0' * n)
	i += 1


t = int(input())
for i in range(t):
	n = int(input())
	q = 10 ** (n - int((n + 1) / 2))
	p = 1
	if n == 1:
		q = 1
	print(p, q)


for tc in range(int(input())):
	n = int(input())
	print(1, 10 ** (n // 2))


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	n = int(input())
	print(1, 10 ** (n // 2))


import math
t = int(input())
for i in range(t):
	n = int(input())
	q = 10 ** (n // 2)
	print(1, q)


for i in range(int(input())):
	n = int(input())
	q = '1' + '0' * (n // 2)
	print(1, q)


t = int(input())
for i in range(t):
	n = int(input())
	print('1 1' + '0' * (n // 2))


T = int(input())
for i in range(T):
	n = int(input())
	if n % 2 == 0:
		p = '1'
		for i in range(1, n // 2 + 1):
			p = p + '0'
		print(1, p)
	else:
		p = '1'
		for i in range(1, (n - 1) // 2 + 1):
			p = p + '0'
		print(1, p)


test_case = int(input())
for i in range(test_case):
	length_of_pin = int(input())
	reverse_length = length_of_pin // 2
	print(1, 10 ** reverse_length)


for i in range(int(input())):
	p = 1
	n = int(input())
	q = pow(10, n // 2)
	print(p, q)


try:
	T = int(input())
	for i in range(T):
		n = int(input())
		print('1', 10 ** (n // 2))
except:
	pass


import math
tt = int(input())
for i in range(tt):
	n = int(input())
	a = n - math.ceil(n / 2)
	print(1, 10 ** a)


import math
tests = int(input())
for i in range(tests):
	num = int(input())
	numerator = num
	if num == 1:
		denominator = num
	else:
		denominator = math.ceil(num / 2)
	gcd = min(numerator, denominator)
	print(10 ** (denominator - gcd), 10 ** (numerator - gcd))


import math
for _ in range(int(input())):
	n = int(input())
	r = n - math.ceil(n / 2)
	print(1, 10 ** r)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	q = 10 ** (n - int((n + 1) / 2))
	p = 1
	print(p, q)


t = int(input())
for i in range(t):
	n = int(input())
	print(1, 10 ** (n // 2))


t = input()
for c in range(0, int(t)):
	n = int(input())
	if n % 2 == 0:
		p = '1'
		for i in range(1, n // 2 + 1):
			p = p + '0'
		print(1, p)
	else:
		p = '1'
		for i in range(1, (n - 1) // 2 + 1):
			p = p + '0'
		print(1, p)


for i in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		x = n // 2
		print(1, 10 ** x)
	else:
		x = (n - 1) // 2
		print(1, 10 ** x)


T = int(input())
for i in range(0, T):
	n = int(input())
	p = 1
	q = 10 ** (n // 2)
	print(p, q)


for i in range(int(input())):
	a = int(input())
	print(1, 10 ** (a // 2))


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		q = 10 ** (n // 2)
	else:
		q = 10 ** ((n - 1) // 2)
	print(1, q)


subtask = int(input())
for _ in range(subtask):
	N = int(input())
	n = N // 2
	n = 10 ** n
	print(1, n)


for _ in range(int(input())):
	N = int(input())
	d = '1' + '0' * (N // 2)
	print(1, d)


T = int(input())
for i in range(T):
	N = int(input())
	p = N // 2
	print(1, 10 ** p)


t = int(input())
for _ in range(t):
	n = int(input())
	if n % 2 == 0:
		val = n // 2
	else:
		val = (n - 1) // 2
	q = '1'
	for _ in range(val):
		q = q + '0'
	print(1, q)


for _ in range(int(input())):
	N = int(input())
	Q = pow(10, N - N // 2 - int(N & 1))
	print(1, Q)


t = int(input())
for _ in range(t):
	n = int(input())
	print(1, '1' + '0' * (n // 2))


t = int(input())
for i in range(t):
	n = int(input())

	def compute_hcf(x, y):
		while y:
			(x, y) = (y, x % y)
		return x
	if n == 1:
		print(1, end=' ')
		print(1)
	elif n > 1:
		a = 0
		b = 10 ** n
		if n % 2 == 0:
			a += 10 ** (n // 2)
		elif n % 2 != 0:
			a += 10 ** (n // 2 + 1)
		hcf = 0
		hcf = compute_hcf(a, b)
		a1 = 0
		b1 = 0
		a1 = a // hcf
		b1 = b // hcf
		print(a1, end=' ')
		print(b1)


try:
	T = int(input())
	for i in range(T):
		N = int(input())
		p = N // 2
		print(1, 10 ** p)
except:
	pass


t = int(input())
while t:
	t -= 1
	n = int(input())
	if n != 1:
		T = int(n / 2)
		p = 1
		q = 10 ** T
	else:
		p = 1
		q = 1
	p = str(p)
	q = str(q)
	print(p, ' ', q)


t = int(input())
for i in range(0, t):
	n = int(input())
	a = n // 2
	b = 10 ** a
	print(1, b)


import math
for h in range(int(input())):
	n = int(input())
	a = math.ceil(n / 2)
	a = n - a
	print('1 1', end='')
	for i in range(1, a + 1):
		print(0, end='')
	print()


from math import pow
from math import gcd
t = int(input())
for ni in range(t):
	n = int(input())
	a = '0' * (n // 2)
	print('1', '1', end='')
	print(a)


for t in range(int(input())):
	n = int(input())
	print('1 ', '1', '0' * int(n / 2), sep='')


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())

def isPalindrome(n: int) -> bool:
	rev = 0
	i = n
	while i > 0:
		rev = rev * 10 + i % 10
		i //= 10
	return n == rev
for _ in range(t):
	n = int(input())
	p = 9
	tot = 9
	q = 0
	flag = 0
	num = 0
	if n == 1:
		print(1, end=' ')
		flag = 1
		print(1)
	else:
		for i in range(2, n + 1):
			if i % 2 == 0:
				pass
			else:
				p *= 10
	if flag == 0:
		q = 10 ** n - 10 ** (n - 1)
		print(str(p // gcd(p, q)) + ' ' + str(q // gcd(p, q)))


for _ in range(int(input())):
	n = int(input())
	num = 1
	den = '1'
	if n % 2 == 0:
		n = n // 2
	else:
		n = (n - 1) // 2
	for _ in range(n):
		den = den + '0'
	print(num, den)


for _ in range(int(input())):
	n = int(input())
	p = 1
	q = 10 ** (n // 2)
	print(p, q)


t = int(input())
for l in range(t):
	n = int(input())
	if n % 2 == 0:
		a = n // 2
	else:
		a = (n - 1) // 2
	s = str(1)
	for b in range(a):
		s = s + '0'
	print(1, s)