Description

在所有的N位正整数中，有多少个数中有偶数个数字3？又有多少个数有奇数个3？由于结果可能很大，你只需要输出这个答案对12345取余的值。

Format

Input

输入一个数N(1<=N<=1000)，以0结束。

Output

对于每一个N位正整数，输出有多少偶数个3以及多少奇数个3，中间用空格隔开。

Samples

2
0

73 17

Limitation

1s, 1024KiB for each test case.