Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
A number game
Time Limit: 2000MSMemory Limit: 32768K
Total Submissions: 504Accepted: 114

Description

The wide dissemination of calculators and computers is not without disadvantages. Teachers all over the world find out that even students in technical disciplines tend to have a surprising lack of calculating ability. Accustomed as they are to the use of calculators and computers, many of them are unable to make calculations like 7*8 mentally, or to factor 91 by heart.
We all know, but who cares?
Professor Bartjens cares. Professor Bartjens is a bit old-fashioned. He decided to give his students some training in calculating without electronic equipment - even without a slide rule. He invented a two-person game involving mental calculations.
Professor Bartjens would write a positive number on the blackboard. During the game more positive numbers may appear on the blackboard. The two players will then make moves in turn. A player on move is obliged to make a move, unless the blackboard is empty, in which case the game is over. A move is one of the following:

If you see the number 1 on the blackboard, you may take it. That means: you gain one point,and the number disappears from the blackboard.
If you see a prime number p on the blackboard, you may subtract one. That is: you gain one point, and the p on the blackboard is replaced by p - 1.
If you see a composite number c on the blackboard, you may replace it by two smaller (positive) numbers, a and b, such that a * b = c. You do not gain any points.

The goal is of course to obtain as many points as you can.
Professor Bartjens was hoping that his students would find the game so interesting that they would spend all day playing, thereby improving their skills in calculation. Indeed his students did find the game interesting, and spent many hours, not so much playing the game as discussing optimal strategies.
The students came to two conclusions. First, the sum of the two players' points after any given game are the same regardless of the actual scheme played. Thus,a player maximising his own points also minimises his opponent's! Second, it is always best to take a point when you have the chance. Thus, whenever prime numbers or ones are written on the blackboard, the player on move takes one of them.
Here is your problem: given a starting number, and assuming both players play to maximise their own points, what will be the outcome?

Input

On the first line of the input is a single positive integer n, telling the number of test scenarios to follow. Each scenario consists of a single line containing the positive integer m < 1000000, the number initially written on the blackboard.

Output

For each test scenario, output one line containing two numbers separated by one space character,equal to the points gained by the two players, both playing to maximise their own points. The first number is the number of points gained by the first player.

Sample Input

6
1
2
3
4
5
6

Sample Output

1 0
1 1
2 1
2 2
3 2
2 3

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator